문제 링크
문제 요약
- 계단을 오르면서, 밟는 계단에 적혀있는 점수를 얻을 수 있다.
- 계단은 한번에 한 칸씩 또는 두 칸씩 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟을 수 없다. 단, 시작점은 포함되지 않는다.
- 마지막 계단은 반드시 밟아야 한다.
풀이
어찌되었든, 구해야하는 것은 최대 점수입니다.
그럼 계단을 밟아야 하고, i번째 계단까지 밟았을 때까지 얻을 수 있는 최대 점수를 구해나가야 합니다.
일단 아래와 같이 DP식을 만들어볼 수 있습니다.
D[i] = i번째 계단까지 밟았을 때, 얻을 수 있는 최대 점수
D[i] = A[i] + max(D[i - 1], D[i - 2)
// A[i] 는 i번째 계단을 밟았을 때 얻는 점수입니다.이제 문제가 생깁니다. 위 DP 식에는 연속된 세 개의 계단을 밟을 수 없다는 조건이 없다. 이 조건을 추가하여 DP식을 개량해야 합니다. 그럼, i번째 계단까지 올라왔을 때, 이전에 몇 개의 연속된 계단을 밟았는지 체크해봅시다.
D[i][j] = i번째 계단까지 이전에 j번 연속되어 밟았을 때, 얻을 수 있는 최대 점수
D[1][0] = ar[1];
D[1][1] = ar[1]; // 시작점은 계단에 포함되지 않습니다.
D[i][0] = A[i] + max(D[i - 2][0], D[i - 2][1]); // i번째 계단까지 밟았을 때, 1번 연속되어 밟았다는 이야기이고 즉, 이전에 건너뛰어 올랐다는 이야기입니다.
D[i][1] = A[i] + D[i - 1][0];정답 코드
#include <bits/stdc++.h>
using namespace std;
int N;
int ar[330];
int D[330][2];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
for(int i = 1; i <= N; i++) cin >> ar[i];
D[1][0] = ar[1];
D[1][1] = ar[1];
for(int i = 2; i <= N; i++) {
D[i][0] = ar[i] + max(D[i-2][0], D[i-2][1]);
D[i][1] = ar[i] + D[i-1][0];
}
cout << max(D[N][0], D[N][1]);
}