[백준 2579/c++] 계단 오르기

다이나믹 프로그래밍을 이용한 문제이다

특이사항으로 1칸, 2칸 씩만 오를 수 있지만 1칸이 연속되면 안된다는 조건이 걸려있다

1칸 연속이 허용되지 않으면 1칸 2칸  혹은 2칸 1칸 혹은 2칸 2칸 의 순으로 가야되는 것인데

2-1 / 1-2 의 경우는 조건에 맞지 않아 문제가 생긴다

1의 위치가 뒤 앞으로 정해지지 않았을때 생기는 문제이니

1 이후에 2가 무조건 오거나 2 이후에 1이 무조건 오도록 오르게 하면 해결된다

하지만 1이후에 2가 무조건 오게 하는 방법은 1만큼 오르는 것이 필수가 아니므로

1-2 / 2-1 / 2- 2 중 일반화 했을때 1이 먼저 오는 1-2 의 경우는  2-2 를 나타내기 힘드므로

2가 먼저 오게 해서 2 이후에 1이 오는 경우, 안오는 경우 2가지만으로 하여 오르는 방법이 올바른 로직이되겠다

2는 중복이 상관없지만 1은 중복하면 안되고 없어도 되기 때문이다

그러므로 2칸 앞에서  2칸 뛰는 경우 score[i - 2] + stair[i]  와

3칸 앞에서 2칸 뛰고 1칸 뛰는 경우 score[i - 3] + stair[i - 1] + stair[i] 중에

더 큰 수를 갖도록 max를 사용하면 되는 문제였다 

-> 항상 bottom 부터 base 값을 할당하여 쌓고, top 을 만족하는 하위 조건들을 생각해낸 후

배열을 이용하여 tabulation 을 사용하여 빠르게 연산하도록 하자 - 다 이 나 믹 프 로 그 래 밍

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

2579번: 계단 오르기

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	int point;
	int stair[304];
	int score[304];
	
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> point;
		stair[i] = point;
	}
	score[1] = stair[1];
    // 1번째도 거쳐 올라오는 게 최대값이다
	score[2] = stair[1] + stair[2];
    // 1-3, 2-3 중 최대값이 score[3]이다
	score[3] = max(stair[1] + stair[3], stair[2] + stair[3]);
	
    // 1이 연속되면 안되므로, n 이전의 도약 시에는 2-n 혹은 2-1-n 의 경우가
    // 있게 된다. 각각 score[n-2]+stair[n] / score[n-3]+stair[n-1]+stair[n]
    // 의 경우를 가지며 이 중 큰 값이 score[n] 을 갖게 된다는 로직이 성립한다
    // 로직은 무조건 2번 뛰는 것부터 시작하므로 1의 중복을 막을 수 있게 된다
	for (int i = 4; i <= n; i++)
	{
		score[i] = max(score[i - 2] + stair[i],
		 score[i - 3] + stair[i - 1] + stair[i]);
	}
	cout << score[n] << "\n";
	return 0;
}