백준 2579번 문제- 계단 오르기

DP

동적 계획법

 

브루트포스 와 백트래킹 지옥에서 빠져나왔다 싶었는데

 

그 다음에 있는것은 DP 지옥이었다.

 

브루트포스와 백트래킹으로는 지나치게 오래걸리는 문제를

 

메모제이션등의 최적화기법을 이용하여 아주 빠르게 값을 찾는다.

 

이는 무지성 코딩에서 한단계 나아가며 훨씬 많은 생각을 요한다.

 

한마디로 어렵다..

 

DP의 핵심은 백트래킹 혹은 재귀함수와 비슷하다.

 

커다란 문제를 작은 문제로 쪼개어 차근차근 풀어간다.

 

풀어가는 도중 나온 결과를 저장하여 연산의 중복을 최소화하고 실행속도를 최적화 한다.

계단 오르기 게임이다.

본격적으로 어려워지는 DP 문제의 시작점이라고 생각한다.

 

계단오르기의 규칙은

 

시작점에서 한칸 혹은 두칸씩 오른다.-> 3칸이상 한번에 뛸수 없다.

세칸을 연속해서 오를수 없다.-> 한칸/한칸/한칸=NG

★마지막칸은 반드시 밟아야한다.

 

세번째 규칙이 있으므로 조금더 편하게 구성할수 있다.

 

큰문제를 작은문제로 쪼갠다.

 

계단이 한개일때의 최댓값

-> 두말할것 없이 첫번째 계단을 밟는 경우 하나

 

계단이 두개일때의 최댓값

->당연히 첫째와 두번째 계단을 밟는 경우 하나

 

계단이 세개일때의 최댓값

->1.첫째,셋째 계단을 밟는 경우

혹은

->2.둘째,셋째 계단을 밟는 경우

(마지막 계단을 반드시 밟아야함으로)

 

.

.

.

이를통해 하나의 규칙을 알 수 있다.

 

계단이 A개일때의 최댓값

=

계단이 A-2 개일때의 최댓값 + 마지막 계단 

혹은

계단이 A-3개일때의 최댓값 + A-1계단 + 마지막 계단

 

이를 바탕으로 코드를 짜보자

 

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

int arr[301] = { 0, }; //문제의 조건은 최대300까지이므로
int sum[301] = { 0, }; //최댓값을 저장할 공간 300개를 만들어 줬다
					   // 1부터 세면 편하니 공간을 하나 더 잡아줌
int main()
{
	
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)  //값을 받는다
	{
		cin>>arr[i];
	}
	sum[1] = arr[1];			//계단 1개일때의 최댓값 저장
	sum[2] = arr[1] + arr[2];   //계단 2개일때의 최댓값 저장
	sum[3] = max(arr[2] + arr[3], arr[1] + arr[3]); //max 함수를 이용하여					
							//두개의 경우의수중 큰값을 저장
	for (int i = 4; i <= n; i++)   //3까진 저장되있으니 4부터
	{
		sum[i] = max(sum[i - 2] + arr[i], sum[i - 3] + arr[i - 1] + arr[i]);
	}      //앞전에 도출해놓은 규칙을 공식으로
	cout << sum[n] << endl;
}

점화식과 일반항을 구하는것은 확실히 어렵다.

하지만 이것이 동적 계획법의 핵심이다.

 

여러가지 유형의 문제를 접하다보면 차차 익숙해지리라고 믿고 있다