[알고리즘] C++ 백준 2579 계단 오르기

 

백준 2579

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

2579번: 계단 오르기

풀이 전 나의 생각

일정 조건에 의하여 계단을 올랐을 때 최대로 나올 수 있는 점수를 얻어야 하는 문제다.

 

조건

1. 한 번에 한 계단, 두 계단 씩 오를 수 있다.

2. 연속해서 3개의 계단을 밟을 수 없다. 

3. 마지막 도착 계단은 반드시 밟아야 한다.

 

이 조건을 의식하면서 처음부터 DP(최대값)를 구해 나가면 생각보다 쉽게 점화식을 구할 수 있다.

문제의 예시인 (10, 20, 15, 25, 10, 20)의 계단 점수를 사용해서 구해보면

DP[1] = Score[1] -> 첫 번째 선택 10 이 최대 값이기 때문에

DP[2] = Score[1] + Score[2] -> 두 번째 계단을 선택했을 때 나올 수 있는 최대 값은 10 + 20 밖에 없다.

DP[3] = max(Score[1] + Score[3], Score[2] + Score[3]) 세 번째 계단을 선택했을 때 나올 수 있는 최대 값 분기는

10, 15를 선택하거나 20, 15를 선택해야 한다.

 

이 세가지를 보면서 알 수 있는 점은 DP[3]부터 max를 써야하니 다음부터는 점화식을 써야만 값이 나올 것이다.

다음으로는 조건 3을 보면 마지막 도착 계단을 반드시 밟아야 하는 조건과 DP 1, 2, 3을 보면 때문에 최대 값을 구하는 식에 무조건 자신의 값이 들어간다. 그렇기 때문에 점화식에도 자기 자신의 값을 더해야 할 것이다.

 

그럼 다음 4번 째 계단을 선택했을 때 나올 수 있는 최대 값의 경우의 수를 생각해보자

10, 20, 25 즉, 1, 2, 4번째 계단을 선택했을 경우와 10, 15, 25 인 1, 3, 4계단을 선택했을 경우 두 가지가 나올 것이다. 

(10, 20, 25) -> 10, 20을 더한 부분은 DP[2]로 대체 가능하기 때문에 DP[2] + Score[4]로 값을 구할 수 있다.

(10, 15, 25)  -> 10을 더한 부분은 DP[1]로 대체 가능하기 때문에 DP[1] + Score[3] + Score[4]로 값을 구할 수 있다.

 

그럼 이를 이용하여  max(DP[N - 2] + Score[N], DP[N - 3] + Score[N - 1] + Score[N])이라는 점화식을 도출해낼 수 있다.

 

최종으로 점화식을 이용하여 계단의 끝까지 탐색하면 점수의 최대 값을 구할 수 있다.

 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>

using namespace std;

int score[301];
int dp[301];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n = 0;
	cin >> n;
	
	for (int i = 1; i <= n; i++)
	{
		cin >> score[i];
	}

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

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

	cout << dp[n];
}