[baekjoon 2579] 계단 오르기 - DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/2579

2579번: 계단 오르기

- 규칙

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

위의 규칙을 통해 두 가지 식을 세울 수 있었다.

 

1. 도착점 기준으로 생각해보는 경우

1. 도착점 전 계단을 밟고 온 경우 : 연속해서 계단 3개를 밟을 수 없기에 전전 계단을 건너뛰고 전전전 계단을 밟은 것으로 생각
2. 도착점 전 계단을 밟지 않고 온 경우 : 전 계단을 밟지 않았기에 전전 계단을 밟고 도착점에 도착한 것으로 생각

DP 배열 : 최댓값을 저장해두는 배열, stair배열 : 입력값 저장 배열

즉, 1의 경우 점화식 : DP[n] = DP[n-3] + stair[n-1] + stair[n]; ( n-2 계단은 밟지 못한다.)

     2의 경우 점화식 : DP[n] = DP[n-2] + stair[n]; (n-1 계단을 밟지 않았기에 두 칸 오른 경우)

 

이렇게 세워두고 두 케이스 중 큰 값을 저장해두면서 진행하면 된다.

 

2. 2차원 배열을 통해 칸 수를 저장해서 구하는 경우

 - 2차원 배열의 구성은 DP [i][2]로 DP[i][1]은 i번째 계단을 한 칸 밟아서 온 경우, DP[i][2]는 i번째 계단을 두 칸 밟아서 온 경우이다.

1. 이번 계단을 한 칸 밟아서 온 경우 이번 값을 계산할 때 전 계단에서 그 계단을 두 칸 밟아서 온 값을 더해준다.
2. 이번 계단을 두 칸 밟아서 온 경우 전전 계단의 값 중 전전 계단을 한 칸 또는 두 칸 밟아서 온 값 중 최댓값을 사용.

말이 너무 어렵다. 식으로 보면

1의 경우 DP[i][1] = DP[i-1][2] + stair[i];

( i번째를 i-1번째에서 올라온 경우, [i-1][1]을 사용 못한다(연속 3칸) 무조건 [i-1][2] 사용)

2의 경우 DP[i][2] = MAX(DP[i-2][1], DP[i-2][2]) + stair[i];

(i번째를 i-2번째에서 올라온 경우, [i-2][1]이나 [i-2][2] 중 최댓값을 사용 가능

 

솔직히 DP 어렵다.. 나도 문제 질문과 블로그를 찾아보면서 풀었다.

나는 두 번째 경우로 풀었다.

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

int stairs[301], n;
int dp[301][2];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> stairs[i];
	}
	dp[1][1] = dp[1][2] = stairs[1];
	for (int i = 2; i <= n; i++) {
		dp[i][1] = dp[i - 1][2] + stairs[i];
		// 방금 한 계단 올라온 경우, 무조건 2계단
		// dp[i][1]은 i번째에 i-1에서 한칸 올라온 것 -> dp[i-1][1]을 사용하면 그 전에도 i-2에서 한칸사용해서 올라온것 -> 연속 3칸 사용.
		dp[i][2] = max(dp[i - 2][1], dp[i - 2][2]) + stairs[i];
		//방금 두 계단 올라온 경우, 1계단 or 2계단 모두 가능
	}

	cout << max(dp[n][1], dp[n][2]);
}