백준 2579. 계단 오르기

www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

2번 조건은 첫번째 계단을 제외하고, 연속으로 1칸을 두번 오를수 없다는 말이다.

1칸 올라가고 또 1칸 올라가고 -> 불가능.

 

n번째 계단을 올랐을때, 1칸으로 올라왔는지, 2칸으로 올라왔는지로 나누어 생각할수 있다.

 

d[n][0] : n번째 계단을 올랐을때, 1칸으로 올라옴, 그때의 총 점수의 최댓값.

d[n][1] : n번째 계단을 올랐을때, 2칸으로 올라옴, 그때의 총 점수의 최댓값.

 

우선 d[1][0], d[1][1]은 첫번째 계단이므로 그냥 첫번째 계단의 점수 stairs[1]이다.

d[2][0] : 1번째 계단에서 1칸으로 올라옴. d[1][0] + stairs[2]

d[2][1] : 0번째 계단에서 2칸으로 올라옴. 그냥 stairs[2]

 

세 번째 계단부터는 케이스를 생각해 봐야한다.

d[3][0] : 2번째 계단에서 1칸으로 올라옴. d[2][1] + stairs[3]

d[2][0] + stairs[3]이 안되는 이유는, 2번 조건때문이다. 연속으로 1칸을 두번 오를수 없기 때문.

d[2][0]은 2번째 계단을 1칸으로 올라왔을때이기 때문에, 이렇게되면 1 -> 2 -> 3 이렇게 연속된 세개의 계단을 밟아버리기 때문이다.

 

d[3][1] : 1번째 계단에서 2칸으로 올라옴. 이때, 첫번째 계단을 1칸으로 올라온경우(d[1][0]), 2칸으로 올라온 경우(d[1][1])을 둘다 생각해야한다.

max( d[1][0] + stairs[3], d[1][1] + stairs[3] )

둘 중 큰 값이 d[3][1]이다. 

 

이렇게 bottom-up으로 n번째 계단까지 쌓아간다. 

 

d[n][0], d[n][1] 중 큰 값이 구하는 값이다.

 

idx	1	2	3	4	5	6
d[n][0]	10	30	35	50	65	65
d[n][1]	10	20	25	55	45	75

 

#include <iostream>
using namespace std;

int stairs[301];
int d[301][2];

int main() {
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++) {
        cin >> stairs[i];
    }

    // d[n][0] : n번째 계단을 올랐을때, 1칸을 오름, 그때의 총 점수의 최대값
    // d[n][1] : n번째 계단을 올랐을때, 2칸을 오름, 그때의 총 점수의 최대값
    d[1][0] = stairs[1];
    d[1][1] = stairs[1];
    d[2][0] = d[1][0] + stairs[2];
    d[2][1] = stairs[2];

    for(int i = 3; i <= n; i++) {
        d[i][0] = d[i-1][1] + stairs[i];
        d[i][1] = max(d[i-2][0] + stairs[i], d[i-2][1] + stairs[i]);
    }

    cout << max(d[n][0], d[n][1]);

}