[C/C++] 백준 #2579 계단 오르기(동적 계획법)

계단 오르기 조건들이 주어지면서, 계단에 적힌 값을 최대, 또는 최소가 되도록 하는 문제들이 꽤 많습니다.

보편적으로 이러한 문제들은 동적 계획법을 이용해서 풀 수 있습니다.

 

climbing the stairs

백준 사이트에서 주어진 문제 링크입니다.

 

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

2579번: 계단 오르기

 

계단 오르기의 조건은 1) 한계단 내지 두계단을 밟을 수 있다.  2) 연속된 3개의 계단을 밟을 수 없다.  3) 도착 계단을 반드시 밟아야 한다. 입니다.

 

이것을 동적 계획법으로 풀기 위해서는 최대의 값을 구하는 식이 필요합니다.  한계단 내지 두계단을 밟을 수 있고, 이전에 한계단을 밟았으면, 다음에는 반드시 두계단을 밟아야 합니다.  \(D_k\)는 k번째 계단을 밟았고, 한계단을 통해서 밟았을 때 최대 점수값을 의미하고, \(T_k\)는 k번째 계단을 밟았고, 마지막에 두계단을 밟은 것이라고 하죠.  그러면, 우리는 \(max(D_n, T_n)\) 을 구하면 됩니다.

\[ D_{k} = T_{k-1} + s_k, D_1 = s_1, D_1 = s_1 + s_2 \]

\[ T_{k} = max(T_{k-2}, D_{k-2}) + s_k, T_1 = s_1, T_2 = s_2 \]  

형태로 계산하시면 됩니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2579
//        - by Aubrey Choi
//        - created at 2019-06-01
//------------------------------------------------
#include <stdio.h>
#include <memory.h>

int max(int a, int b)
{
    return (a > b) ? a : b;
}

int main()
{
    int n;
    int s[300];
    int save[2][300];
    memset(save, 0, sizeof(save));
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &s[i]);
    }
    save[0][0] = s[0];
    save[1][0] = -1000000;
    save[0][1] = s[1];
    save[1][1] = s[0] + s[1];
    for(int i = 2; i < n; i++)
    {
        save[0][i] = max(save[0][i - 2], save[1][i - 2]) + s[i];
        save[1][i] = save[0][i - 1] + s[i];
    }
    printf("%d\n", max(save[0][n-1], save[1][n-1]));
    return 0;
}