백준 2579번 :계단 오르기( 다이나믹 프로그래밍)

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

2579번: 계단 오르기

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

이번 문제의 조건 이다

다이나믹 프로그래밍은 큰 문제를 작은 문제로 쪼개서 만드는 것이고, 이 문제 또한 사용한다.

첫번째 조건 중에 한 계단 씩 두 계단 식 오른다고 했는데 그 식을 만들어 보면

d[i][j]은 i번쨰 계단에 올라왔을 떄 j개 연속해서 올라온 계단 이다.

d[i][1]는 1개 연속 이므로 i-1번쨰는 밟으면 안되고 i-2번쨰는 2개 연속이든 1개 연속이든 상관이 없다.

즉 max(d[i-2][1],d[i-2][2])+a[i](현재 계단 점수)

d[i][2]는 2개 연속이므로 반드스 i-1번째에 1개 연속이어야한다.

즉 d[i-1][1]+a[i]

이 방식으로 구현 해보면 코드는 아래와 같다

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#define PI 3.1415926535
using namespace std;

int main()
{
	int d[301][3] = { 0 };
	int a[301] = { 0 };
	int n;
	int k;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	d[1][1] = a[1];
	for (int i = 2; i <= n; i++) {
		d[i][1] = max(d[i - 2][1] , d[i - 2][2])+a[i];              //i번쨰가 1번 연속으로 밟았을 경우
		d[i][2] = d[i - 1][1]+a[i];                                   //i번쨰가 2번 연속으로 밟았을 경우
	}
	cout << max(d[n][1], d[n][2]);
	return 0;
}