C++) 백준 2579번 풀이_계단 오르기

 

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

2579번: 계단 오르기

ㅋ ㅋ...ㅋㅋㅋ 장난

 

 

끝 계단을 꼭 올라야 한다는 거에 사로잡혀서 끝부터 계산한다고 삽질했다.

 

규칙을 그래프로 그려서 덩어리로 뭉뚱그리는게 훨 편하다고 생각하게 된 문제

 

n번째 계단을 밟는 경우는

1. n-1번째 계단을 밟고 올라온 경우와

2. n-2번째 계단을 밟고 올라온 경우가 있는데

 

여기서 n-1번째 계단을 밟는 경우는

1-1. n-3번째 계단을 밟고 올라오는 경우

밖에 없다.

3계단을 한 번에 올라갈 수가 없기 때문에,

n-2를 밟았을 경우 n-2 -> n-1 -> n번째 계단을 밟는다는 과정이 성립되지 않기 때문.

 

n-2번째 계단을 밟는 경우는 딱히 제한이 없으므로

2-1. n-3번째 계단을 밟고 올라오는 경우

2-2. n-4번째 계단을 밟고 올라오는 경우

로 나누어 짐.

 

이걸 그림으로 그려보면

이렇게 되는데 

 

여기서 패턴을 찾으면

이런 느낌(...)

 

이걸 식으로 나타내면

 

S[i]= val[i]+val[i-1]+S[i-3] or val[i] + S[i-2]

 

하게끔 코드를 짜면 됩니다.

 

#include<stdio.h>
#include<algorithm>

using namespace std;

int main(void) {
	int i, cnt;
	int inp[301];
	int cal[301];

	scanf("%d", &cnt);

	for (i = 1; i <= cnt; ++i)
	{
		scanf("%d", &inp[i]);
	}

	cal[1] = inp[1];
	cal[2] = inp[1] + inp[2];
	cal[3] = max(inp[2] + inp[3], inp[1] + inp[3]);

	for (i = 4; i <= cnt; ++i)
	{
		cal[i] = max(inp[i] + inp[i - 1] + cal[i - 3], inp[i] + cal[i - 2]);
	}

	printf("%d", cal[cnt]);
}