2579번 : 계단 오르기

Backjoon Online Judge 

"2579번 : 계단 오르기" 문제입니다.

문제 링크 : https://www.acmicpc.net/problem/2579

문제에서 선택된 수의 최대값을 구하기 위해 DP를 이용하였습니다.

규칙 파악을 하기위해 k번째 계단을 올랐을때 최댓값을 구했습니다.

(k번째 계단의 점수를 s(k), k번째 계단의 점수의 합을 ms(k)로 표시합니다.)

1번째 계단까지 올라갔을 때 최댓값 : s(1)

2번째 계단까지 올라갔을 때 최댓값 : s(1)+s(2)

3번째 계단까지 올라갔을 때 최댓값 : max( [ s(1)+s(2) ] , [ s(2)+s(3) ] )

(1,2,3번째 계단을 모두 오를 수 없으므로)

이때 3번째 계단에 오르게 되는 경우의 수는

1. 이전 계단을 밟고 올라옴. [s(2)를 포함]

2. 이전 계단을 밟지 않고 올라옴. [s(2)를 포함하지 않음] 으로 나뉩니다.

1의 경우 이전 계단과 현재 계단을 밟으므로 2칸 아래 계단을 밟을 수 없고 3칸 아래 계단에서 최대 점수를 얻었을때 최대 점수를 얻을 수 있습니다.

2의 경우 이전 계단을 밟지 않았으므로 그 이전 계단까지 최대 점수를 얻으면 k번째 계단에서 최대 점수를 얻을 수 있습니다.

이를 일반화 해서 표현하면

k번째 계단까지 올라갔을 때 최댓값은

max( [ ms(n-3) + s(n-1) + s(n) ] , [ ms[n-2] + s(n) ] ) 이 됩니다.

아래는 코드 설명입니다.

 - 각 계단의 점수와 각 계단 위치에서 최댓값을 저장하기 위해 각각 score[Max]와 maxScore[Max] 배열을 선언했습니다.

 - 이후 maxScore[2]까지는 초기값으로 직접 값을 넣어주고 maxScore[3]부터는 위의 공식을 통해 계산하였습니다. 

코드는 C++로 작성하였습니다.

#include <iostream>
#include <algorithm>
#include <memory.h>
 
#define MAX 301
 
using namespace std;
 
int main() {
    int stair;
    int score[MAX];
    int maxScore[MAX];
 
    cin >> stair;
    score[0] = 0;    // 시작지점
    for(int i = 1; i <= stair; i++) {
        cin >> score[i];
    }
 
    maxScore[0] = 0;    // 시작 지점
    maxScore[1] = score[1];
    maxScore[2] = score[1] + score[2];
    //maxScore[3] = max(score[1] + score[3], score[2] + score[3]);
 
    for (int i = 3; i <= stair; i++) {
        maxScore[i] = max(maxScore[i - 2], maxScore[i - 3] + score[i - 1]) + score[i];
    }
    cout << maxScore[stair] << endl;
}