[백준/C언어] 2579번 - 계단 오르기

백준 웹사이트 "2579번 - 계단 오르기" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

2579번: 계단 오르기

---

소스 코드

#include <stdio.h>

int max(int a, int b);

int main(void){
    int N;  //계단 수
    scanf("%d", &N);

    int stairs[N];
    for(int i=0; i<N; i++){
        scanf("%d", &stairs[i]);
    }

    //score[i][0]: 바로 전 계단을 밟았을 때, i+1번째 게단에서 얻을 수 있는 최대 점수
    //score[i][1]: 바로 전 계단을 건너뛰었을 때, i+1번째 게단에서 얻을 수 있는 최대 점수
    //score[n+2][0] = score[n+1][1] + stairs[n+2]
    //score[n+2][1] = max(score[n][0], score[n][1]) + stairs[n+2]
    //최종 답: max(score[N-1][0], score[N-1][1])

    int score[N][2];
    score[0][0] = stairs[0], score[0][1] = stairs[0];
    score[1][0] = stairs[0] + stairs[1], score[1][1] = stairs[1];
    //printf("stair 1: %d\nstair 2: %d\n", max(score[0][0], score[0][1]), max(score[1][0], score[1][1]));

    for(int i=2; i<N; i++){
        score[i][0] = score[i-1][1] + stairs[i];
        score[i][1] = max(score[i-2][0], score[i-2][1]) + stairs[i];
        //printf("stair %d: %d\n", i+1, max(score[i][0], score[i][1]));
    }

    printf("%d\n", max(score[N-1][0], score[N-1][1]));
}

int max(int a, int b){
    if(a>b)
        return a;
    else
        return b;
}

---

문제 풀이

  'stairs[N]'은 각 계단에 쓰여있는 점수이며, 'stairs[i]'는 i+1번째 계단의 점수를 의미합니다.

  'score[N][2]'는 바로 전 계단을 밟았을 때/밟지 않았을 때 i+1번째 계단에서 얻을 수 있는 최대 점수를 의미합니다.

  이렇게 두 가지 배열을 정의한 뒤, 아래와 같은 계획을 세울 수 있습니다.

 

//score[i][0]: 바로 전 계단을 밟았을 때, i+1번째 게단에서 얻을 수 있는 최대 점수
//score[i][1]: 바로 전 계단을 건너뛰었을 때, i+1번째 게단에서 얻을 수 있는 최대 점수
//score[n+2][0] = score[n+1][1] + stairs[n+2]
//score[n+2][1] = max(score[n][0], score[n][1]) + stairs[n+2]
//최종 답: max(score[N-1][0], score[N-1][1])

 

  score[i][0], score[i][1]은 각각 전 계단을 밟았을 때/밟지 않았을 때의 최대 점수입니다. 세 개의 계단을 연속해서 밟을 수 없다는 조건이 있으므로 다음과 같은 점화식을 세울 수 있습니다.

$$ score[n+2][0] = score[n+1][1] + stairs[n+2] $$

$$ score[n+2][1] = max(score[n][0], score[n][1]) + stairs[n+2] $$

  바로 전 계단을 밟았을 경우 전전 계단은 밟지 않았어야 하므로 \(score[n+1][1]\)을 이용해주고, 전 계단을 밟지 않았을 경우 전전 계단을 밟았어야 하므로 \(max(score[n][0], score[n][1])\)을 이용해줍니다. 동적 계획법을 이용해 score 배열을 빠르게 채울 수 있습니다.

  마지막 계단은 반드시 밟는다는 조건에 의해, 최종 답은 \(max(score[N-1][0], score[N-1][1])\)이 됩니다. Overflow가 일어나는 경우가 있는지 확인하는 것이 좋은데, 모든 계단의 점수를 합해도 최대 300 × 10,000을 넘지 못하므로, int 범위 내에서 충분히 해결 가능합니다.​