[BOJ2579] 계단오르기

[BOJ2579] 계단오르기

문제링크

문제설명

• 0에서 시작하여 계단을 오르는데 계단은 한번에 한 칸내지 두 칸을 오를 수 있다. 또한 연속된 계단 3개는 오를 수 없다.(첫 번째 계단, 두 번째 계단, 세 번째 계단으로는 오를 수 없음.)
• 마지막 계단에 도착을 무조건 하여야 하고, 마지막 계단에 도착하였을 때 계단에 쓰여있던 점수들의 최대 합을 구하는 문제이다.

코드리뷰

• DP를 이용하여 풀었는데, 처음 시작할 때 시작점에서 첫번째 계단을 밟고 시작하는 경우, 첫번째 계단을 밟지않고 두번째 계단을 밟고 시작하는 경우가 있다.
• 마찬가지로, 어떤 계단(i)에 올라갈땐 (i-1)계단을 밟고 올라가는 경우와 (i-2)를 밟고 올라가는 경우가 있다.
• 마지막 계단(n)에 도착할 때도, n-1계단을 밟고 올라가는 경우와 n-2계단에서 바로 올라가는 경우가 있다.
• 나는 DP배열을 2차원으로 만들어서 DP[0][i] 일 경우는 i-1을 밟지않고 i로 올라온 경우로, DP[1][i] 는 i-1을 밟고 온 경우로 만들었다.
• 인덱스가 0인 경우는 이전 계단을 밟지 않은 dp배열, 1인 경우는 이전 계단을 밟은 dp배열이 된다.
• 이런식으로 n까지 dp배열을 쌓으면, dp[0][n] (n-1계단을 밟지 않고 온 경우)와 dp[1][n] (n-1계단을 밟고 온 경우) 두가지로 나뉠 것이다. 그 두가지중 최대 값을 출력하였다.
• 다른 분들 풀이를 보니 dp를 1차원으로 해결하였는데, 다음 번엔 1차원으로 다시 한번 구현해보아야겠다.

#include <iostream>
#include <algorithm>
using namespace std;

int stair[305];
int dp[2][305];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> stair[i];
	}
	dp[0][1] = stair[1];
	dp[0][2] = stair[2];
	dp[1][2] = dp[0][1] + stair[2];
	for (int i = 3; i <= n; i++) {
		if (dp[0][i - 2] > dp[1][i - 2]) dp[0][i] = dp[0][i - 2] + stair[i];
		if (dp[0][i - 2] <= dp[1][i - 2]) dp[0][i] = dp[1][i - 2] + stair[i];
		dp[1][i] = dp[0][i - 1] + stair[i];
	}
	int result = max(dp[0][n], dp[1][n]);
	cout << result << '\n';
	return 0;
}