백준 2579번 : 계단 오르기

링크 : 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번째 칸까지 고려해야 하므로 점화식을 사용한다.

• N-2칸을 밟고 N칸을 밟는 경우 : N-2칸까지의 최댓값 + 현재 N칸 값
• N-3칸을 밟고 N-1칸을 밟고 N칸을 밟는 경우 : N-3칸까지의 최댓값 + N-1칸 값 + N칸 값

for (int i = 3; i < N; i++) {
	dp[i] = max(dp[i - 2] + arr[i], arr[i - 1] + arr[i] + dp[i - 3]);
}

---

에잇 아쉽다. 하지만 다음에 이 문제를 가지고 응용해서 풀 수 있었으면 좋겠다. 꽤 고생한 문제다.