백준 2579 - 계단 오르기

문제 번호: 2579

문제 제목: 계단 오르기

문제 주소: https://www.acmicpc.net/problem/2579

문제 내용

계단을 올라갈 때마다 밟을 칸의 점수를 획득한다. 도착지점까지 오르면서 얻을 수 있는 최고 점수를 출력한다.
단, 계단은 한 칸 또는 두 칸 간격으로 올라갈 수 있으며 연속해서 세 개를 밟을 수는 없다.

테스트 케이스

6 10 20 15 25 10 20	75
1 10	10
2 10 20	30
3 10 20 30	50
6 10 15 20 10 25 20	80

문제 풀이

최대 이동 간격이 두 칸이라는 점, 연속해서 세 개의 계단을 밟을 수 없다는 점이 풀이의 핵심이다.
N번째 위치에 도달하는 경우는 직전에서 올라오는 경우, 두 칸 전에서 올라오는 경우로 나뉜다.
직전에서 올라오는 경우에는 직전 칸 도달의 최대값을 현재 칸 값에 더하면 되고, 
두 칸 전에서 올라오는 경우에는 세 칸 전 도달의 최대값 + 두 칸 전의 계단값에 현재 칸 값을 더하면 된다.

이미지로 표현하면 아래 두 가지 경우 중에 큰 값을 최대값 n에 넣는 것과 같다.

풀이 코드

#include <iostream>
using namespace std;

void BAEKJOON_2579()
{
	int N;
	cin >> N;
	int stairs[301];
	int dp[301] = { 0 };
	for (int i = 1; i <= N; i++)
	{
		cin >> stairs[i];
	}
	/*-----------------점화식 및 계산------------------*/
	dp[1] = stairs[1];
	dp[2] = stairs[1] + stairs[2];
	for (int i = 3; i <= N; i++)
	{
		int left = stairs[i] + dp[i - 2];
		int right = stairs[i] + stairs[i - 1] + dp[i - 3];
		dp[i] = left > right ? left : right;
	}
	/*-----------------출력--------------------*/
	cout << dp[N] << endl;
	return;
}