[백준 2579] 계단 오르기

문제설명

규칙에 알맞게 주어진 입력값에 대해서 구해 낼 수 있는 최대값을 출력한다

계단의 수가 주어지고, 각 계단마다의 값이 주어진다

계단은 한번에 한칸 또는 두칸씩 오를 수 있으며, 세칸연속 밟는것은 불가능하다

그리고 마지막엔 반드시 마지막 칸을 밟아야한다

알고리즘

1. 계단의 각 정보를 입력 받는다

2. 3번째 계단까지 따로 계산해 둔다

3. 반복문을 통해서 n 번째 계단까지 구한다

4. n번째 계단의 값을 구한다

코드

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

int stair[301];

int dp[301];

int main() {
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> stair[i];
	dp[1] = stair[1];
	dp[2] = stair[1]+stair[2]; //최대값은 무조건 여기까지 왔을 때 첫번째를 밟은것 
	dp[3] = max(stair[1] + stair[3], stair[2] + stair[3]); //둘중 큰 것
	//전칸을 밟았을때와 밟지 않았을때 

	for (int i = 4; i <= n; i++)
		dp[i] = max(dp[i - 2] + stair[i], dp[i - 3] + stair[i - 1] + stair[i]);
	cout << dp[n];
}

고찰

이번 문제는 다이나믹프로그래밍 알고리즘을 활용한 문제이다

주어진 조건을 지켜서 마지막 계단에 도달했을 때, 최대값을 계산해야한다

이때 가장 주의해야할 조건은 마지막 계단을 반드시 밟아야 한다는 것이다

따라서 마지막 계단을 밟을 때를 기점으로 식을 세울 수 있다

 

dp[ i ] = dp [ i-2] + stair[ i ] (도착점 전칸을 안밟은 경우)

dp[ i ] = stair [ i] + stair [ i-1] +dp [i-3]  (도착점 전칸을 밟은 경우)

 

위 두식은, 마지막 칸 까지의 값을 구하기위한 식이다

두 식을 계산해서 가장 큰 값이 결과 값이 된다  

먼저 첫번째 식의 경우 전 칸을 밟지 않은 경우 이므로 전전칸의 값에, 마지막 값을 더한다

두번째 식의 경우 전 칸은 밟은 경우 이므로 전칸 + 현재칸 + 전전전 칸을 더한다