2) 백준 2579 - 계단 오르기

<문제>

www.acmicpc.net/problem/2579

2579번: 계단 오르기

그동안 거의 웹만 했음...ㅎㅎㅎ...... 앞으로 자주 올...(크흠..)려야지 ㅎㅎㅎㅎㅎ

 

<코드>

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	int N;
	cin >> N;
	
	int stair[300] = {0, };
	
	for(int i = 0; i < N; i++) {
		cin >> stair[i];
	}
	
	int max_stair[300] = {0, };
	
	max_stair[0] = stair[0];
	max_stair[1] = max(stair[1], stair[0]+stair[1]);
	max_stair[2] = max(max_stair[0]+stair[2], stair[1]+stair[2]);
	
	for(int i = 3; i < N; i++) {
		max_stair[i] = max(max_stair[i-3]+stair[i-1]+stair[i], max_stair[i-2]+stair[i]);
	}
	
	cout << max_stair[N-1] << endl;
	
	return 0;
}

처음엔 어떻게 해야할지 고민이 많았다....

그런데 하나하나 적어보면서 생각하니 풀리기 시작했다.

 

배열에 하나하나 적어가면서 계단의 갯수에 따라서 최댓값을 저장해둬서 후에 다시 쓰는 방법으로 계산을 했다.

그런데 연속으로 3개의 계단은 밟을 수 없으므로 다음을 생각해주자.

 

i번째 계단 전에 밟은 계단이....??

1. i-2 번째 계단이라면

2. i-1 번째 계단인데 그 전에 i-3 번째 계단을 밟았다면

3. i-1 번째 계단인데 그 전에 i-2 번째 계단을 밟았다면

 

1.

최댓값을 저장해둔 배열에서 index가 i-2번에 있는 수는 i-2번째 계단을 밟았을 때 최댓값이 저장되어 있다.

이 수를 그냥 i 번째 계단을 더해주면 i번째 계단에서 가질 수 있는 최댓값 후보가 하나 생겼다.

2.

그 전에 i-3번째 계단을 밟았으므로 i-1번째 다음에 i번째 계단을 밟을 수 있다. 1번의 방법과 비슷하게 i-3번째 계단을 밟았을 때 최댓값에서 i-1번째와 i번째 계단을 밟으므로 이 둘의 값을 더해주면 또 다른 최댓값 후보가 또 하나 생겼다.

3.

i-1번째 계단 전에 i-2번째 계단을 밟으면 i 번째 계단은 밟을 수 없으므로 패스!

 

1번과 2번의 값을 비교해서 더욱 큰 값을 index = i 인곳에 넣어주면 된다.

이를 N번 반복해서 index가 N인 곳을 출력해주면 끝!

 

DP.... 너무 어려워...ㅠㅠㅠㅠㅠㅠ