2579번 : 계단 오르기

2006년 초등부 지역본선 4번 문제입니다.

조건을 다시 되짚어보면

한번에 최대 두 칸 위까지 올라갈 수 있다.

연달아 3칸을 밟으면 안된다.

도착 지점은 무조건 밟아야 한다.

dp는 i번째 계단을 밟을때와 밟지 않을 때 각각의 최대 점수를 dp로 쌓아주시면 됩니다.

즉 dp[3][1]은 3번째 칸을 밟았을 때 최대 점수이고, dp[3][0]은 3번째 칸을 밟지 않았을 때(건너 뛰었을 때)의 최대 점수입니다.

0. dp[0][0], dp[0][1], dp[1][0]은 0으로 초기화, dp[1][1]은 1번 칸 값으로 초기화.

1. 해당 칸을 밟지 않았을 때는 그 전칸은 무조건 밟았다는 소리가 됩니다. 따라서 dp[i][0]은 dp[i-1][1]이 됩니다.

2. 해당 칸을 밟았을 때는 dp[i-1][0]과 dp[i-1][1] 중 큰값에 해당 칸 점수를 부여합니다.

이때 3칸을 연속으로 밟았을 때(dp[i-3][0]+stair[i-2]+stair[i-1]+stair[i]가 dp[i][1]과 같다면), 

dp[i][1]=MAX(i-2번째 칸과 i번째 칸을 밟았을 때 , i-2번째 칸을 밟지 않고 i-1번째 칸과 i번째 칸을 밟았을 때)로 설정합니다.

#include <stdio.h>

int dp[301][2];

int stair[301];

int N;

int MAX(int a, int b) {

return a > b ? a : b;

}

int main() {

scanf("%d", &N);

for (int i = 1; i <= N; ++i) {

scanf("%d", &stair[i]);

}

dp[0][0] = 0;

dp[0][1] = 0;

dp[1][0] = 0;

dp[1][1] = stair[1];

for (int i = 2; i <= N; ++i) {

dp[i][0] = dp[i - 1][1];

dp[i][1] = MAX(dp[i - 1][1] + stair[i], dp[i-1][0]+stair[i]);

if (i >= 3) {

if (dp[i][1] == dp[i-3][0]+stair[i] + stair[i - 1] + stair[i - 2]) {

dp[i][1] = MAX(dp[i - 2][1] + stair[i], dp[i - 2][0] + stair[i-1] + stair[i]);

}

}

}

printf("%d", dp[N][1]);

}