BOJ - 2579 계단 오르기 해결 전략 (C++)

• 문제 링크 : 백준 2579번 - 계단 오르기

해결 전략

  본 문제는 아주 기초적인 DP 문제이다. 기초 문제임에도 포스팅을 하는 이유는, 본인이 4번 제출해서 3번을 틀렸기 때문이다(부끄럽다..)

  본 문제의 핵심은 다음과 같다.

계단 i의 점수와, i를 포함한 i까지의 누적 스코어를 개별로 두고 점화식을 세워야 한다.

  배열 2개 혹은 구조체를 통해 해결할 수 있으리라. 본인이 실수한 지점은, 3개 연속 계단 조건의 처리 방법인데, 최초 3회 시도에서 본인은 구조체에서 former_pos라는 필드를 두어 이전 max 선택 인덱스를 기억시키는 방식을 택했었다. 이렇게 하니 식도 길어지고 실수의 여지가 커져버렸다.

그냥 점화식 자체로 '3개 연속 계단 불가 조건'을 처리하면 되지 않는가?

  3회째 해결 실패를 맞이하고서야 위와 같은 생각이 떠올랐다. 왜 굳이 어렵게 풀었던 것일까. 본 문제에 대한 설명은 여기까지면 충분하다고 느낀다. 아래는 코드이다.

#include <iostream>
#include <algorithm>
// BOJ - 2579 Going up the stairs
using namespace std;

typedef struct _step {
	int key;
	int score;
}Step;

Step stairs[301];

int solve(int n) {
	stairs[0].key = stairs[0].score = 0; stairs[1].score = stairs[1].key;
	stairs[2].score = stairs[1].key + stairs[2].key;

	for (int i = 3; i <= n; i++) 
		stairs[i].score = max(stairs[i].key + stairs[i - 1].key + 
			stairs[i - 3].score, stairs[i].key + stairs[i - 2].score);

	return stairs[n].score;
}

int main(void) {
	int n;
	
	cin >> n;
	for (int i = 1; i <= n; i++)  cin >> stairs[i].key;
	cout << solve(n);

	return 0;
}