[C++] 백준 2579번 계단 오르기

계단을 밟아서 최대 점수를 만드는 다이나믹 프로그래밍 문제입니다.

 

규칙으로는

1. 한번에 한 계단 또는 두 계단씩 오를 수 있습니다.

2. 연속된 세 계단을 밟으면 안됩니다.

3. 마지막 계단은 꼭 밟아야 합니다.

 

memo[i][j]에 계단의 점수를 저장해서 문제를 풀었습니다.

memo[i][j]에서 i는 몇번째 계단인지를 나타냅니다.

                    j는 1이면 연속 1번 계단을 밟은 상태,

                    j가 2면 연속 2번 계단을 밟은 상태를 나타냅니다.

 

현재 1번연속으로 밟은 상태일때 가능한 경우는 2칸 점프를 했을때 입니다.

memo[i][1] = max(memo[i-2][1], memo[i-2][2]) + stair[i]; 

2칸 전 상태에서 2번연속일때와 1번 연속일때 중 더 큰 점수인 경우를 가져와서

현재 계단의 점수값과 합칩니다.

 

현재 2번연속으로 밟은 상태일때 가능한 경우는 1번연속인 상태에서 1칸 이동했을때 입니다.

memo[i][2] = memo[i-1][1] + stair[i]; 

1칸 전 상태에서 현재 계단의 점수값을 합친 값을 저장합니다.

 

각 계단에 대한 최대로 얻을 수 있는 점수를 저장하고

마지막 계단을 올랐을 때 저장된 값을 뽑아내면서 결과를 얻어냅니다.

 

#include  
using namespace std; 

int stair[200]; 
int memo[200][3]; 

void init() // 초기화
{ 
    for(int j=0; j<3; ++j){ 
        for(int i=0; i<200; ++i){ 
            memo[i][j] = 0; 
        } 
    } 
    for(int i=0; i<200; ++i){ 
        stair[i] = 0; 
    } 
} 

int main(int argc, char *argv[]) 
{ 
    int cycle; // 계단 수
    cin >> cycle; 
    init(); 
    for(int i=0; i<cycle; ++i){ 
        cin >> stair[i]; 
    } 
    memo[0][1] = stair[0]; // 초기 값
    memo[1][1] = stair[1]; 
    memo[1][2] = stair[0] + stair[1]; 
    for(int i=2; i<cycle; ++i){ 
        memo[i][1] = max(memo[i-2][1], memo[i-2][2]) + stair[i]; // i계단에 대해 연속 1번일때의 점수값
        memo[i][2] = memo[i-1][1] + stair[i];                          // i계단에 대해 연속 2번일때의 점수값
    } 
    cout << max(memo[cycle-1][1], memo[cycle-1][2]);  // 마지막 계단에서 연속 1번일때와 2번일때 중 큰값을 출력
    return 0; 
}