[알고리즘 문제] 백준2579 - 계단 오르기

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

2579번: 계단 오르기

각각의 계단하다 점수가 적혀있고 다음 3가지의 조건을 만족하면서 계단 끝까지 올랐을 때 최대점수를 구하는 문제입니다.

 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

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

 

2개의 배열을 사용하며 arr[]에는 숫자를 입력받으며 dp[i]에는 i번째 계단에 도달할 때의 최대 점수를 저장합니다.

 

그렇다면 dp[5] : 45라는 것은 무엇을 의미할까요 ?

1계단에서 5계단까지 위의 조건을 만족하면서 이동할 수 있는 방법이 4가지가 있다고 해봅시다. 각각의 방법의 점수합은 다를 것입니다. 경로가 다르니깐요. 그 중에 점수합이 가장 큰 값이 dp[5]에 저장됩니다.

 

dp[5] : 45를 다시 말해보면 1~5계단까지 조건을 만족하면서 이동할 수 있는 여러 방법중에 점수합이 가장 큰 경우가 45라는 것입니다. 

 

그럼 이제 dp[5]의 정의를 알았으니 구하는 방법을 알아 봅시다.

문제 조건에서 n번 위치에서 이동할 수 있는 방법은 n+1로 가거나, n+2로 가거나 둘 중 하나를 선택해야 합니다. 그리고 n, n+1, n+2이런 순서로 연속된 세개의 계단을 밟아서는 안되구요.

 

그러면 5번째 계단에 접근할 수 있는 방법은 다음과 같습니다. 아래 두개의 경우 중 최대값은 dp[5]에 넣으면 됩니다.

 

1. 2번째 계단에서 3번째 계단은 건너고 4,5번째 계단에 접근하는 방법 : dp[5] = dp[2] + arr[4]+arr[5]

2. 3번째 계단에서 4번째 계단은 건너고 5번쨰 계단에 접근하는 방법 : dp[5] = dp[3] + arr[5]

 

--> dp[i] = max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i]);

 

계단 오르기 문제는 2156 포도주 시식 문제와 거의 비슷한데, 계단 오르기 문제는 매 순간 한칸씩 올라가야 하지만 포도주 시식은 n번째 포도주를 마시지 않아도 된다. 그렇기 때문에 dp[i] = d[i-1]의 경우를 추가해야 한다. 이는 i번째 포도주를 마시지 않기 때문에 이전의 경우를 그냥 가져오게 된다.

#include <iostream>
#include <algorithm>

using namespace std;

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

    int arr[301] = {0};
    long long dp[301] = {0};

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

    dp[1] = arr[1];
    dp[2] = arr[2] + arr[1];

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

    // dp[i-2] + arr[i] : i-2번째 i번째 칸에서 오는 경우
    // dp[i-3] + arr[i-1] + arr[i] : i-1번째 칸에서 i번째로 오는 경우
    cout << dp[n];

    return 0;
}