JArchive 프로그래밍 일기

문제

계단 오르기 백준 2579번

리뷰

점화식을 구하는 데 조금 헤맸다.

계단이 1, 2, 3, 4번이 있고, 만약 현재 4번째 계단에 위치한다면,

max(2번째 계단까지의 최대값 + 4번째 계단점수 , 3번째 계단까지의 최대값 + 4번째 계단점수)

이렇게 비교해서 4번째 계단까지의 최대값을 구할 수 있을 줄 알았는데, 틀렸다.

이유는 4번이 마지막 계단(반드시 밟아야 하는 계단) 이라면,

2번을 밟고 4번을 밟았는지, 1번, 3번을 밟고 4번을 밟았는지를 비교해야 했다.

(OXOO or OOXO )

3번을 밟은 경우에는, 반드시 1번을 밟고 온 경우만 고려해야 한다. (왜냐하면 1, 2, 3 연속으로 밟으면 안되기 때문이다. )

case1) 1번 계단까지의 최대값 + 3번 계단점수 + 4번 계단점수

case2) 2번 계단까지의 최대값 + 4번 계단점수

이 두 가지의 경우를 비교하면서 DP로 푼다.

// i : 도착 계단 (반드시 밟아야함)

    case1 = D[i-3] + S[i-1] + S[i]; 
    case2 = D[i-2] + S[i];

코드

#include <stdio.h>
#include <algorithm>
using namespace std;

int S[301]; // i번 계단의 점수 
int D[301]; // i번 계단까지의 최대점수 기록 

int Max(int stair_size){

    int i = 0;
    int case1, case2 = 0;

    for(i=3; i<= stair_size; i++){

        case1 = D[i-3] + S[i-1] + S[i];
        case2 = D[i-2] + S[i];

        D[i] = max(case1, case2);

    }

    return D[stair_size];
}

int main(void){

    freopen("input.txt", "rt", stdin);

    int stair_size, i = 0, num = 0;

    scanf("%d", &stair_size);

    for(i = 1; i <= stair_size; i++){
        scanf("%d", &num);
        S[i] = num; // 계단의 점수 입력받음 
    }

    D[1] = S[1];
    D[2] = D[1] + S[2];

    printf("%d", Max(stair_size));

    return 0;
}