[BOJ] 2579 계단 오르기 - 동적계획법

 

어떠한 인덱스 N에 도착하기 위한 경우의 수는 두가지 밖에 없다.

두칸 전에서 두칸을 뛰어 오르던지,

한칸전에서 한칸을 뛰어 오르던지.

근데 두칸을 올라서 굳이 한칸을 빼먹어야 될 일은 없다.

그래서 무조건 한칸씩 계속 오르면 최대값이다.

다 올라간게 무조건 최대값이다.

이건 문제가 되질 않는다.

그래서 문제에선 세칸이 연속되면 안된다는 조건을 건다.

 

두칸전에서 두칸을 뛰어 오르는 경우를 생각해보자.

이건 단순히 N - 2 번째 칸까지의 최대값에서, N 칸을 밟은 거다.

두칸을 올라온 거니 따로 제약사항이 없다.MAX(N) = MAX(N-2) + COST(N)이 나온다.

 

한칸전에서 한칸을 뛰어 오르는 경우를 생각해보자.

여긴 조건이 있다.따라서 패턴을 강제시킨다.

 

N - 1 번째 칸에서 한칸을 뛰어 올랐다면, N - 1번째 칸은 밟아야한다.

N - 2 번째 칸은 무조건 밟아서는 안된다. 조건에 위배된다. N번째 칸을 밟고있는 상태라는것을 기억하자.

N - 3 번째 칸은 무조건 밟아야 한다 왜 ? 그래야 두칸을 뛰어올라 N - 1 번째 칸을 밟을수 있다.

 

N - 1 번째 칸을 밟는 경우엔 반드시 위와 같이 나올수 밖에 없다.단 한가지다. 이 패턴을 강제시킨다.

 

N - 3 번째까지의 최대값을 구할때 이전패턴이 어떤것인지는

이전에 최대값을 계산할때 비교하고, 적용 되었을 것이다.

따로 신경쓰지 않는다.

패턴을 강제하는건 N - 1 과 N - 2 에 대해서이다. 

강제시킨 패턴의 식은 다음과 같이 나온다.

MAX(N) = MAX(N-3) + COST(N) + COST(N-1)

식을 구성할수 있으니, 반복문에 적용해 아래 인덱스부터 차례대로 답을 구한다.

코드는 다음과 같이 작성하였다.

#include <algorithm>
#include <iostream>
int MaxSumUntil[301]				= { 0, };
int Cost[301]						= { 0, };
 
int main()
{
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin.sync_with_stdio(false);
	std::cout.sync_with_stdio(false);
	
	int N;
	std::cin >> N;
 
	for (int i = 1; i <= N; ++i)
		std::cin >> Cost[i];
 
	MaxSumUntil[1] = Cost[1];
	MaxSumUntil[2] = Cost[1] + Cost[2];
	MaxSumUntil[3] = std::max(Cost[1] + Cost[3], Cost[2] + Cost[3]);
 
	for (int i = 4; i <= N; ++i)
		MaxSumUntil[i] += Cost[i] + std::max(MaxSumUntil[i - 3] + Cost[i - 1], MaxSumUntil[i - 2]);
 
	std::cout << MaxSumUntil[N] << std::endl;
 
	return 0;
 
}