[C++][백준 2579][다이나믹 프로그래밍] 계단 오르기 :: seoftware

 문제 

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

2579번: 계단 오르기

 방안 

매번 말하는 거지만 dp는 무조건 배열과 관계식이다!

배열과 관계식을 따로 설명을 하자면,

1. 배열 : steps 배열과 scores 배열을 생성하였다. steps는 계단 점수를 입력받는 배열이고, scores는 다이나믹 프로그래밍의 결과를 저장할 배열이다. scores의 규칙은 2번 관계식에서 설명할 것이다.
2. 관계식 : '마지막 계단은 밟지 않는다'는 조건과 '세 계단을 연속으로 밟을 수 없다'는 조건을 고려하여 관계식을 세워야 한다. 마지막 계단은 꼭 밟아야 하므로 steps[n]은 항상 더해진다. 세 계단을 연속으로 밟을 수 없으므로 이전 계단을 밟은 경우와 밟지 않은 경우로 케이스를 분류한다.

<마지막 계단(n) 이전 계단(n-1)을 밟은 경우>
세 계단 연속으로 밟을 수 없으므로 이전 계단의 이전 계단(n-2)는 무조건 못 밟고,
그 전 계단(n-3)은 무조건 밟는다.
따라서, scores[n] = scores[n-3] + steps[n-1] + steps[n]

<마지막 계단(n) 이전 계단(n-1)을 밟지 않은 경우>
이전 계단의 이전 계단(n-2)는 무조건 밟는다.
따라서, scores[n] = scores[n-2] + steps[n]

결과적으로 scores[n] 은 위 두 케이스 중에서 더 큰 값으로 결정하면 된다.
scores[n] = max(scores[n-3] + steps[n-1] + steps[n], scores[n-2] + steps[n]); 

 소스 

#include <iostream>
#include <algorithm>
using namespace std;
int steps[301];
int score[301];
int main(void) {
	int k;
	cin >> k;

	
	for (int i = 1; i <= k; i++) {
		int input;
		cin >> input;
		steps[i] = input;
	}
	score[0] = 0;
	score[1] = steps[1];
	score[2] = steps[1] + steps[2];
	for (int i = 3; i <= k; i++) {
		score[i] = max((score[i - 3] + steps[i - 1] + steps[i]), (score[i - 2] + steps[i]));
	}
	cout << score[k];
	return 0;
}