[백준] 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;
}