[2579] 계단 오르기

---

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

2579번: 계단 오르기

DP 문제인데 어려워서 검색함

ㅎㅎ

내 무궁한 발전을 위해 어쩔 수 없는 선택이었당~!

 

 

여기서 조건 3가지가 쓰여있다.

1. 계단은 한 번에 1, 2칸씩
2. 시작점 제외하고 연속해서 3계단 밟지 마라
3. 마지막 도착 계단은 밟아라

 

 

마지막 계단에 도착한다고 했을 때 2가지 경우가 존재한다.

1. 바로 전 계단을 밟고 마지막 계단 도착

  -> 이 경우에는 전전계단을 밟으면 안된다(2번 조건 때문). 그러므로 전전전계단을 밟아야 함

DP[i] = DP[i - 3] + A[i - 1] + A[i];

2. 전전 계단을 밟고 마지막 계단 도착

DP[i] = DP[i - 2] + A[i];

DP[i] : i번째 계단까지의 최댓값

1번 경우/2번 경우

그림으로 표현하면 위와 같다.

 

 

우리는 항상 최댓값을 원하므로 max함수를 이용하여 둘 중의 최댓값을 DP[i]에 담아줘야 한다.

그렇게 완성된 코드는 아래와 같다.

#include <iostream>
#include <cmath>
using namespace std;

// 1. 계단은 한 번에 1, 2칸씩
// 2. 시작점 제외하고 연속해서 3계단 밟지 마라
// 3. 마지막 도착 계단은 밟아라

int N;
int A[301]; int DP[301]; // i번째 계단에서의 최댓값

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

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

	// 초기값 설정
	DP[1] = A[1];
	DP[2] = max(A[1] + A[2], A[2]); // 시작->1->2번째 계단 or 시작->2번째 계단
	DP[3] = max(A[1] + A[3], A[2] + A[3]); // 시작->1->3번째 계단 or 시작->2->3번째 계단 비교

	for (int i = 4; i <= N; i++) {
		int d1, d2;
		d1 = DP[i - 3] + A[i - 1] + A[i]; // 바로 전계단 밟음(그러면 전전전계단을 밟아야하므로 i-3)
		d2 = DP[i - 2] + A[i]; // 전전계단 밟음
		DP[i] = max(d1, d2);
	}

	cout << DP[N];
}