[BOJ] 2579 계단 오르기 c++ (DP)

 

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

 

✔ 문제이해

한번에 한 계단 or 두 계단 씩 오를 수 있고

연속된 세 개의 계단을 밟을 수 없고

마지막 도착 계단은 반드시 밟아야 한다.

라는 세가지 규칙을 가진 계단 오르기 게임이 있다.

 

계단의 수와 계단들의 값이 주어진다. 규칙을 지키며 계단을 오를때 계단들의 값을 더하고 최대 값을 구하여라.

 

✔ 풀이+코드

계단의 값을 모아둔 배열을 arr, 계단의 최대값을 모아둔 배열을 DP라고 했을때, 아래 그림을 보자.

 

세 칸 올랐을 때부터 두가지 경우가 생긴다.

1. 두 계단으로 올라오는 경우

2. 연속으로 한 계단씩 밟고 올라오는 경우

이 두가지 경우를 max로 최대값을 구하여 풀어준다.

 

한 칸 올랐을 때 DP[1] = arr[1]

두 칸 올랐을 때 DP[2] = arr[1] + arr[2]

세 칸 올랐을 때 DP[3] = max(arr[1], arr[2]) + arr[3]이 된다.

 

n으로 일반화를 한다면,

DP[n] = max(DP[n-3] + arr[n-1] , DP[n-2]) + arr[n]이 된다.

(사진과 식의 순서가 바뀌어 있긴 합니다. ㅎㅎ)

 

#include <iostream>
using namespace std;

int N;
int arr[301];
int DP[301];

int main()
{
    cin >> N;
    for(int i = 1; i <= N; i++)
    {
        cin >> arr[i];
    }

    DP[1] = arr[1];
    DP[2] = arr[1] + arr[2];
    DP[3] = max(arr[1], arr[2]) + arr[3];

    for(int i = 4; i <= N; i++)
    {
        DP[i] = max(DP[i-3] + arr[i-1], DP[i-2]) + arr[i];
    }

    cout << DP[N]  << endl;
    return 0;
}

 

✔ 피드백

• DP풀이가 생각났다면 1부터 시작하여 규칙을 찾아보자

✔ reference

https://velog.io/@gonudayo/%EB%B0%B1%EC%A4%80-2579-%EA%B3%84%EB%8B%A8%EC%98%A4%EB%A5%B4%EA%B8%B0-2156-%ED%8F%AC%EB%8F%84%EC%A3%BC-%EC%8B%9C%EC%8B%9D