[DP] BOJ 2579번 문제풀이

문제 분석 

 

각 계단을 오를 때 계단에 적혀있는 숫자의 합이

가장 큰 경우를 구하는 문제다.

 

조건은 다음과 같습니다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

자, 지금부터

 

s[i] = 계단의 적힌 숫자

 

d[i][j] = 현재까지 j 개의 계단을 연속해서 밟고, i 번째 계단에 

올라섰을 때의 점수 합의 최댓값이라고 합시다.

(단, i 번째 계단은 반드시 밟는다.)

 

이상태에서 주어진 계단에 대해서 한번 값을 찾아봅시다.

 

첫 번째 계단에서는 이러한 값이 도출됩니다.

d[1][1] = s[1] , d[1][2] = 0

d[1][1] 은 자명하게 s[1] 이라는 것을 알 수 있습니다. 

또한, d[1][2] 은 불가능하기 때문에 d[1][2] = 0 으로 둡시다.

※ 현재 설명은 이해를 돕기위해 1-indexed 기반의 설명을 하지만, 코드는

0-indexed 기반으로 되있습니다.

두 번째 계단에서는 

d[2][1] = s[2], d[2][2] = s[1] + s[2]

d[2][1] 은 두 번째 계단까지 한 개의 계단을 밟았다는 의미이므로 첫 번째 계단을 

안 밟았다는 의미가 된다.

반대로 d[2][2] 는 두 개의 계단을 밟았기 때문에 첫 번째, 두 번째 계단을 모두 

밟았다는 의미가 된다.

세 번째 계단에서는

d[3][1] = max( d[1][1], d[1][2]) ) + s[3]

d[3][2] = d[2][1] + s[3]

d[3][1] 부터는 경우의 수가 나뉜다. 계단을 한번 연속적으로 밟았기 때문에 

직전 계단인 s[2] 을 밟지 않았다는 의미가 된다.

그러면 d[1][1] 와 d[1][2] 두 가지의 경우의 수가 나뉘고 그중 

최댓값에 마지막 계단을 더해주면 된다.

 

d[3][2] 같은 경우는 무조건 이전 계단인 s[2]를 밟았으며 

이미 연속적으로 2번을 밟은 상태이므로 d[2][1]의 경우만

존재한다.

 

여기까지 이해하셨다면 반드시

계단그림을 그려보고

경우의 수를 따져보시길 바랍니다. (꼭)

 

이제 점화식이 감이 오나요?

 

d[i][1] = max( d[i-2][1], d[i-2][2] ) + s[i]

d[i][2] = d[i-1][1] + s[i]

 

이러한 점화식이 나왔다면 처음에 

상수값으로 도출되는 초깃값을 정의해주시고

코드를 짜 보신다면 

 

답을 맞히실 수 있을 겁니다.

 

코드

 

#include "bits/stdc++.h"

using namespace std;
int d[301][2];
int n;
int s[301];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> s[i];
	}
	d[0][0] = s[0];
	d[0][1] = 0;
	d[1][0] = s[1];
	d[1][1] = s[0] + s[1];

	for (int i = 2; i < n; i++)
	{
		d[i][0] = max(d[i - 2][0], d[i - 2][1]) + s[i];
		d[i][1] = d[i - 1][0] + s[i];
	}
	cout << max(d[n - 1][0], d[n - 1][1]);

}