링크 : https://www.acmicpc.net/problem/2579
다이나믹 프로그래밍이다.
한번에 1 계단 또는 2 계단을 오를 수 있다. 하지만 연속 3개의 계단을 모두 밟아서는 안된다. 시작점은 이에 포함되지 않고 마지막 도착 계단은 반드시 밟아야 한다. 따라서 마지막 부분을 밟을 수 있도록 잘 계산해야 겠다.
총 점수의 최댓값을 구해보자.
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int N;
int arr[300]{ 0, };
int dp[300]{ 0, };
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
dp[0] = arr[0]; // base case
dp[1] = max(arr[0] + arr[1], arr[1]);
dp[2] = max(arr[0] + arr[2], arr[1] + arr[2]);
for (int i = 3; i < N; i++) {
dp[i] = max(dp[i - 2] + arr[i],
arr[i - 1] + arr[i] + dp[i - 3]);
}
cout << dp[N - 1];
return 0;
}
우선 첫번째로 접근했을 때에는 무조건 마지막 계단을 밟아야 하니 stack을 이용하여 마지막 계단에서 첫번째 계단으로 접근하려고 했었다. 그러다보니 0번째 계단에서 되는 경우 O-X-O
와 되지 않는 경우 O-O-O
를 예외점으로 두어야 해서 계속 틀리게 나왔다. 또한 N+2번째 계단으로 갈 때까지의 다양한 경우의 수를 생각했어야 했는데 그러지 못했다.
가장 큰 실수는 밟지 않고 넘어가는 계단이 연속되는 경우를 제외하지 않았다.
참고한 블로그는 다음과 같다. 링크 : https://kwanghyuk.tistory.com/4
점화식으로 구현한다.
0번째 칸은 계산할 필요 없으므로 그대로 가져간다.
1번째 칸의 경우 0번째 칸을 밟아도, 안밟아도 되므로 계산하여 가져간다.
2번째 칸의 경우 0번째 칸을 밟고 바로 2번째 칸으로 올 수도 있고, 0번째 칸을 밟지 않고 1번째 칸을 밟아 2번째 칸으로 올 수 있다.
dp[0] = arr[0]; // base case
dp[1] = max(arr[0] + arr[1], arr[1]);
dp[2] = max(arr[0] + arr[2], arr[1] + arr[2]);
여기까지는 전의 2개만 고려하면 되므로 base case로 떼어둔다.
이후부터는 전의 3번째 칸까지 고려해야 하므로 점화식을 사용한다.
for (int i = 3; i < N; i++) {
dp[i] = max(dp[i - 2] + arr[i], arr[i - 1] + arr[i] + dp[i - 3]);
}
에잇 아쉽다. 하지만 다음에 이 문제를 가지고 응용해서 풀 수 있었으면 좋겠다. 꽤 고생한 문제다.