[C/C++ 백준 2579번] 계단 오르기 (Silver 3)

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

전에 파도 뭐시기랑 같은 실버3인데, 고민을 훨씬 많이 하게 되는것 같다. 같은 티어가 맞냐 이게???

일단 생각한 아이디어는, 재귀함수를 이용하여 두 가지 경우중 더 큰 쪽으로 리턴하는 것이다.

A

B

사진을 붙여서 넣고 싶은데, 티스토리가 처음이라 어떻게 옆에 붙여 넣을 수 있는지 모르겠다.

저 마지막 도착점에 도달하기전 마지막으로 밟는 계단은, 위의 25과 15 둘 중 하나다. 그러니까 도착점(N)에 도달하기 전까지 N-2번째까지 최대 점수, N-1번째 계단과 N-3번째까지의 최대 점수 합중 더 큰것과 N번째 계단을 합해 리턴시키면 된다. 이걸 코드로 구현해 보면, 

 

#include <stdio.h>
int func(int gaedan[], int where){
    if(where<0)
        return 0;
    else if(where==1)
        return gaedan[1]+gaedan[0];
    else if(where==0)
        return gaedan[0];
    else{
        if(func(gaedan, where-2)>func(gaedan, where-3)+gaedan[where-1])
            return func(gaedan, where-2)+gaedan[where];
        else
            return func(gaedan, where-3)+gaedan[where-1]+gaedan[where];
    }
}
int main(void){
    int N, gaedan[301]={};
    scanf("%d",&N);
    for(int i=0; i<N; i++){
        scanf(" %d", &gaedan[i]);
    }
    printf("%d",func(gaedan, N-1));
}

결과는 시간초과. 사실 딱 봐도 엄청 오래걸릴거 같은 코드이긴하다. 여러 글들을 보니, 하위 계단의 여러 func들은 중복으로 호출되는 경우가 생기는데, 그걸 배열로 한번만 처리되게 하면 시간이 확실히 줄어든다고 한다. 난 왜 이 생각을 못했지?

 

#include <stdio.h>
#define max(a,b) ((a > b) ? a : b)
 
int main(void){
    int N, gaedan[301]={};
    int memory[301]={};
    scanf("%d",&N);
    for(int i=1; i<=N; i++){
        scanf(" %d", &gaedan[i]);
        if(i==0)
            memory[i]=0;
        else if(i==1)
            memory[i]=gaedan[i];
        else if(i==2)
            memory[i]=gaedan[i]+gaedan[i-1];
        else
            memory[i]=max(memory[i-2], memory[i-3]+gaedan[i-1])+gaedan[i];
    }
    printf("%d",memory[N]);
}

memory 배열을 만들어서 위의 함수를 써준다. 해결!