백준 2579 계단 오르기(c++)

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

2579번: 계단 오르기

<코드>

#include <iostream>
#include <algorithm>
#define max 301
int dp[max];
int arr[max];
using namespace std;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>arr[i];
	}
	dp[1] = arr[1];
	dp[2] = arr[1] + arr[2];
	dp[3] = arr[1] + arr[3] > arr[2] + arr[3] ? arr[1] + arr[3] : arr[2] + arr[3];
	
	for(int i=4;i<301;i++)
	{
		dp[i] = dp[i-2] + arr[i] >dp[i-3] + arr[i] + arr[i-1] ? dp[i-2] + arr[i] : dp[i-3] + arr[i] + arr[i-1]; 	
	}
	cout<<dp[n]; 
}

<문제 풀이>

dp[1] => 첫번째 계단을 올랐을때

dp[2] => 첫번째 계단 + 두번째 계단

dp[3] => max(첫번째 계단 + 세번째 계단, 두번째 계단 + 세번째 계단)

dp[4] => max(첫번째 계단 + 두번째 계단 + 네번째 계단, 첫번째 계단 + 세번째 계단 + 네번째 계단)

으로 생각할 수 있다.

왜냐하면 계단은 세 번 연속 뛸 수 없으며 최대 두 칸이기 때문에, 이전 값을 이용해서 최댓값을 구하는 dp를 통해 구현할 수 있다.