[C/C++] 백준 2579번 - 계단 오르기(DP)

 

<코드>

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

int N;
int Stairs[302];
int DP[302];

//점화식 DP[i] = max(DP[i - 2] + Stairs[i], DP[i - 3] + Stairs[i] + Stairs[i - 1]);
int main()
{
	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> Stairs[i];


	DP[1] = Stairs[1];
	DP[2] = Stairs[1] + Stairs[2];

	for (int i = 3; i <= N; i++)
		DP[i] = max(DP[i - 2] + Stairs[i], DP[i - 3] + Stairs[i] + Stairs[i - 1]);
	

	cout << DP[N];

		
}

 

문제 조건

1. 연속으로 3계단을 오를 수는 없다.
2. 한 번에 한 계단 혹은 두 계단을 오를 수 있다.
3. 마지막 계단을 무조건 밟아야 한다.

 

풀이 방법

cocoon1787.tistory.com/194

[C/C++] 백준 2156번 - 포도주 시식(DP)

위 링크 문제풀이 일부분 캡처

 

 

며칠 전에 풀었던 포도주 시식 문제와 비슷한 맥락으로 풀이가 가능하다. 다만 차이점은 포도주 문제의 경우 마지막 잔을 꼭 마시지 않아도 되지만 이번 문제는 마지막 계단을 꼭 밟아야 하는 문제 조건이 있다.

따라서 점화식을 생각해보면

• i-3번째 계단을 밟는 경우는 DP[i-3] + Stairs[i-1] + Stairs[i]
• i-2번째 계단을 밟는 경우는 DP[i-2] + Stairs[i] //(i-2, i-1, i번째를 연속으로 밟을 수 없다.)
• i-1번째를 밟는 경우는 DP[i-3]에 포함되므로 고려하지 않는다.

따라서 아래와 같은 식으로 DP값을 구할 수 있다.

DP[i] = max(DP[i - 2] + Stairs[i], DP[i - 3] + Stairs[i] + Stairs[i - 1]);

 

 

 

www.acmicpc.net/problem/2579

2579번: 계단 오르기