[백준 BOJ] 2579 : 계단 오르기 (C++)

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

아이디어 흐름

1. 아이디어 구상

이전에 풀었던 dp문제들에 견주어 이 문제 또한 '내가 i번째에 있을 때 이것을 선택할때, 하지 않을 때' 라는 측면에서 먼저 생각해보았다. 세 가지를 연속으로 선택할 수 없다는 조건을 생각해보고 

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

위와 같이 (i - 2), (i - 1), i 중 합이 더 큰 두 개의 값과, 이미 최댓값으로 구해왔을 dp[i - 3]을 더하여 dp[i]를 구해주려 하였다.

2. 초기 아이디어의 한계, 수정

하지만 위 점화식대로라면 '세 가지를 연속으로 선택할 수 없다' 는 조건을 제어해줄 수가 없었다.

예를 들어 이번 i 번째 인덱스에서 최대값으로 arr[i - 1] + arr[i] 을 선택하여 dp[i]를 구했다고 하자. 인덱스가 증가하여 dp[i + 3]을 구하러 왔을 때 arr[i + 1] + arr[i +2] 이 둘을 선택하는 것이 최댓값일 경우 dp[i + 3]에서는 결국 (i - 1), i, (i + 1), (i + 2) 를 모두 선택하는 상황이 돼버린다. 때문에 점화식을 아예 다시 생각해보기로 하였다.

문제를 다시 읽은 후 하나의 정보를 더 발견하였다. 마지막 원소는 꼭 선택해야하므로 max((arr[i - 2] + arr[i - 1]), (arr[i - 2] + arr[i]), (arr[i - 1] + arr[i])) 에서 (arr[i - 2] + arr[i - 1]) 는 고려할 필요가 없다.

그 후 dp[i] = dp[i - 3] + max((arr[i - 2] + arr[i]), (arr[i - 1] + arr[i])) 로 돌아와보니 '아 어차피 모든 경우에 대해서 마지막 원소는 선택하게 되어있으니깐 (arr[i - 2] + arr[i]) 이렇게 선택하는 경우는 dp[i - 2] + arr[i] 와 같은 의미구나' 라는 사실을 발견했고 최종적으로 점화식을 

dp[i] = max((dp[i - 3] + arr[i - 1] + arr[i]), (dp[i - 2] + arr[i])) 다음과 같이 변경하였다.

3. 코드

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

int main(){
	int arr[301];
	int dp[301];
	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	dp[0] = arr[0];
	dp[1] = arr[0] + 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 - 3] + arr[i - 1] + arr[i]), (dp[i - 2] + arr[i]));
	}
	cout << dp[N - 1] << '\n';
}

4. 아쉬운점

• 총 소요시간 : 50분
• 아이디어 구상 : 35분
• 구현 : 15분

점화식을 세우고 수정하고 구현하는 과정 자체에 불필요한 과정은 없었다고 생각한다. 하지만 막상 구현이 끝난 후 돌아보니 아이디어와 코드가 너무나 간단해보인다. 다음에 dp를 풀게 되면 최대한 빠르게 문제 조건에 맞는 점화식을 세우도록 노력해야겠다.