백준 2579번 계단 오르기 (DP)

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

2579번: 계단 오르기

 

DP(Dynamic Programming)문제를 풀어보자.

문제에서 중요한 포인트가 있는데, 연속 두 계단씩 오를 수 있으며 마지막 도착계단은 반드시 밟아야 한다.

이 부분을 생각해서 점화식을 세워야 한다.

 

결국 마지막 계단을 밟아야하는데, 이 때 두가지의 경우로 나뉘게 된다.

  1) 마지막 이전 계단을 밟았을 때

  2) 마지막 이전 계단을 밟지 않았을 때

 

1)의 경우 마지막 계단은 무조건 밟아야하므로 연속 두번 밟게 되므로, 전전계단은 밟지 말아야 한다.

따라서 전전전계단을 밟았을 때의 최대값(D[N-3])에서 전 계단(P[i-1])과 마지막 계단(P[i])을 밟았을 때의 점수를 더하면 된다.

 --> D[N] = P[i] + P[i-1] + D[N-3] 

 

2)의 경우 마지막 이전 계단을 밟지 않았으므로 전전계단을 밟았을 때의 최대값(D[N-2])에서 마지막 계단(P[i])의 값을 더해주면 된다.

 --> D[N] = P[i] + D[N-2]

 

이를 소스코드로 구현하면 아래와 같다.

 

 

<소스코드>

#include<iostream>
#include<algorithm>

using namespace std;

int p[301];
int d[301];

int main(void) {
	int n;
	cin >> n;

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

	d[2] = p[1] + p[2];
	d[1] = p[1];

	for (int i = 3; i <= n; i++) {
		d[i] = max(p[i] + p[i - 1] + d[i - 3], p[i] + d[i - 2]);
	}

	cout << d[n] << '\n';

	return 0;
}