[C++] 백준 #2579 : 계단 오르기

문제설명

풀이과정

오랜만에 풀어보는 DP 문제였다. 처음에는 마지막 계단을 기준으로 DP를 진행하려고 했으나...뭔가 할수록 고려해야할 사항이 많아져서 아니다 싶었다. 그래서 그냥 첫 계단을 기준으로 DP를 했다.
사실 1번 규칙을 잘 이해하지 못했다. 1번 규칙을 보면,

"한 계단을 밟으면서"

라는 말이 있는데, 이 말은 즉 첫 번째 계단은 무조건 밟아야함을 의미한다.

따라서 각 계단에서의 최대 점수를 DP[ ]로 만들어서 DP를 진행했다.

자세한 풀이과정은 다음과 같다.

(배열의 인덱스는 0부터 시작하지만 헷갈리지 않기 위해 arr[1]부터 입력받았다.)

1. DP[1]은 arr[1]일 것이다.
2. DP[2] = arr[1] + arr[2]이다.
3. DP[3] = max(DP[2], arr[1] + arr[3] 이다.

그리고 이후 계단에서의 최대 점수는

DP[i] = max(DP[i - 2] + arr[i], DP[i -3] + arr[i] + arr[i + 1]

이다.

연속해서 세 개의 계단은 밟지 못하니까
(자신의 두 칸 아래에서의 최댓값 + 자신의 점수) 와
(자신의 세 칸 아래에서의 최댓값 + 자신의 점수 + 자신 바로 아래칸의 점수)
중의 최댓값이 곧 그 칸에서의 최댓값이기 때문이다.

소스코드

#include <bits/stdc++.h>
using namespace std;

int arr[305];
int dp[305];

int main() {
	ios::sync_with_stdio(false);

	int n;

	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	dp[1] = arr[1];
	dp[2] = arr[1] + arr[2];
	dp[3] = max(arr[2] + arr[3], arr[1] + arr[3]);




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

	cout << dp[n];

	return 0;
}

피드백

DP는 너무 복불복이다ㅠㅠ한번 눈 트이면 쭉쭉 풀리는데 거기까지 가는게 어려울 뿐...