[백준] 2579번: 계단 오르기 [C++]

 

알고리즘 분류: 다이나믹 프로그래밍

문제 링크: https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

 

【 풀이 】

 

이 문제 역시 동적계획법(DP)을 이용하여 해결하는 문제이다. 또한 문제의 규칙성을 찾는 것이 굉장히 중요하다.

우선, 본인은 계단의 수가 5일 때까지 계단을 오르는 모든 경우의 수를 구해보았다.

 

계단의 점수를 저장해놓은 배열 stair과

경우의 수에 따라 계단의 점수를 더한 것 중 최댓값을 저장하는 배열 score를 선언한다.

계단의 수는 5개라고 하자. 경우의 수는 다음과 같이 나열된다.

 

• 1번 계단을 반드시 밟는 경우: 1
• 2번 계단을 반드시 밟는 경우: 1-2
• 3번 계단을 반드시 밟는 경우: 1-3, 2-3
• 4번 계단을 반드시 밟는 경우: 1-2-4, 1-3-4, 2-4
• 5번 계단을 반드시 밟는 경우: 1-2-4-5, 1-3-5, 2-3-5

 

여기서 다시 정리하면,

 

• score[1] = stair[1]
• score[2] = score[1] + stair[2]
• score[3] = score[1] + stair[3] 또는 score[2] + stair[3] (둘 중 최댓값)

1,2,3 은 이렇게 정의되고

 

• score[4]
  • 1-2-4: score[2] + stair[4]  ( score[2] = score[1] + stair[2] ) 
  • 1-3-4: score[1] + stair[3] + stair[4]
• score[5]
  • 1-3-5와 2-3-5: score[3] + stair[5]  ( score[3] 에서의 최댓값 + stair[5] )
  • 1-2-4-5: score[2] + stair[4] + stair[5]

4,5는 이렇게 정의된다.

계단의 수를 N이라고 했을 때, 이를 점화식으로 일반화시키면 다음 두 가지 식이 나온다.

 

• score[N] = score[N-2] + stair[N]
• score[N] = score[N-3] + stair[N-1] + stair[N]

 

그리고 위의 점화식을 바탕으로 Bottom-Up으로 구현했다.

 

 

 

【 코드 】

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

int score[301];
int stair[301];
int main(void)
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> stair[i];
	
	score[1] = stair[1];
	score[2] = stair[1] + stair[2];
	score[3] = max(stair[1] + stair[3],stair[2]+stair[3]);

	for (int i = 4; i <= n; i++)
	{
		int a = score[i - 2] + stair[i];
		int b = score[i - 3] + stair[i - 1] + stair[i];
		score[i] = max(a, b);
	}
	cout << score[n];
	return 0;
}