2579) 계단 오르기 (C++)

 출처 

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

2579번: 계단 오르기

 내 풀이 

#include<iostream>

using namespace std;

int stairs[301];	//입력 받을 계단
int result_stairs[301];	//결과로 출력할 계단 

int N = 0;

int main()
{
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> stairs[i];
	}

	result_stairs[1] = stairs[1];
	result_stairs[2] = stairs[1] + stairs[2];
	result_stairs[3] = stairs[3] + max(stairs[1], stairs[2]);

	for (int i = 4; i <= N; i++)
	{
		result_stairs[i] = stairs[i] + max(result_stairs[i - 2], 
       		result_stairs[i - 3] + stairs[i - 1]);
	}

	cout << result_stairs[N];

}

 

 해설

다이나믹 프로그래밍으로 풀리는 문제였다. 먼저 조건을 보면 

 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

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

 

이를 토대로 각 계단이 최대값이 되는 공식을 적어보았다.

 

1 = 1

2 = 2 + 1 

3 = 3 + 1 OR 2 큰값  

4 = 4 + 2 + 1 OR 4 + 3 + 1 

5 = 5 + 2 + 3 OR  5 + 4 + 2 + 1

6 = 6 + 4 + 3 + 1 OR 6 + 5  + 3 + 2 

 

예제입력 1을 예제로 풀어보면

계단 수 6, 계단 1부터 -> 10 20 15 25 10 20

 

1 = 10

2 = 20 + 10 => 30

3 = 15+ 10 OR 20 큰값 => 35 

4 = 25 + 20 + 10 OR 25 + 15 + 10 => 55

5 = 10 + 20 + 15 OR 10 + 25 + 20 + 10 => 65

6 = 20 + 25 + 15 + 20 OR 20 + 10 + 15 + 20 => 75 

 

좌측 4, 5, 6 번째 계단을 확인하여 보면 

20+10=30, 20+15=35, 25+15+20=55 -> 최댓값을 구한 N-2계단의 값이 그대로 가져와 지는걸 확인할 수 있다. 

즉 좌측은 N + MAX(N-2)가 성립한다.

 

우측 4, 5, 6 번째 계단을 확인하여 보면 

15+10, 20+20+10, 10+15+20 파란색은 바로 직전 N-1값, 초록색은 최댓값을 구한 N-3값이 온다는걸 확인할 수 있다.

즉 우측은 N + MAX(N-3) + N-1가 성립한다.

 

따라서 N = N + max( MAX(N-2) , MAX(N-3) + N-1) 이라는 공식을 사용하여 문제를 풀었다. 

 

 

 새로 안 것 

자신감 하락 이게 실버3이 맞냐..