[백준 2579번/C언어] 계단 오르기, 동적계획법으로 풀이

백준 2579번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 문제 내용이 길어 따로 캡쳐본을 첨부하지 않았으니, 링크를 참고하면서 봐주시면 됩니다.

백준 2579번: https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

이 문제 역시 이전에 업로드한 피보나치 수열과 마찬가지로 동적계획법 학습을 위해 푼 문제입니다. 따라서 동적계획법에 익숙하지 않으시다면, 아래 블로그를 참고해 주시기 바랍니다. 저 역시 동적계획법 문제를 처음 접해보기 때문에 다양한 글들을 꼼꼼히 읽어본 후, 가장 기초적인 문제부터 풀고 있습니다. 이 문제 역시 기초적인 문제에 해당하지만, 동적계획법에 익숙하지 못한 탓인지 점화식을 찾는 데에 긴 시간을 소비했습니다. 

https://didu-story.tistory.com/220

[알고리즘] Dynamic Programming (동적 계획법, DP) (feat. Swift 스위프트)

 

 

동적계획법을 이용하기 위해서는 우선 점화식(Recurrence Relation)을 먼저 파악할 수 있어야 합니다. 사실 동적계획법의 가장 기초이자 까다로운 부분은 이 점화식을 파악하기 전에 이 문제가 동적계획법에 해당하는지를 알아내는 것이라고 하는데요, 이것도 동적계획법 문제를 많이 봐야 인지할 수 있다고 하니 저는 우선 잘 알려진 동적계획법 문제를 많이 접하는 것부터 시작하고자 했고, 따라서 저의 첫 번째 단계는 점화식을 발견해 내는 것이었습니다. 

 

점화식을 파악하기 위해 우선 예제 입력의 경우를 쭉 줄지어 써보았습니다. 

예제 입력의 경우 아래와 같습니다.

시작 - 10 - 20 - 15 - 25 - 10 - 20 - 끝

 

위 입력, 즉 같은 데이터를 가지고 n이 0일 때부터 5일 때(우리가 최종적으로 구하고자 하는 경우)까지를 줄지어 써보았습니다. 그 결과는 아래와 같습니다. 

S(0) = 0
S(1) = 10
S(2) = 10 + 20 = 30
S(3) = 20 + 15 = 35
S(4) = 10 + 20 + 25 = 55
S(5) = 10 + 20 + 25 + 20 = 75 

 

이렇게 적어보면서 발견한 첫번째 규칙은 n-1번째 계단과 n-2번째 계단은 결코 같이 더해질 수 없다는 것입니다. (당연한 얘기입니다. 3개의 계단이 연속으로 선택될 수 없으니까요.) 따라서 우리는 우리가 n-1 계단을 선택하는 경우와 그렇지 않은 경우, 이렇게 두 가지의 경우로 나누어 볼 수 있습니다. n-1번째 계단을 선택하는 경우라면 n-2번째 계단을 건너뛰고, n-3번째 계단까지의 최댓값을 더해주면 됩니다. 그렇지 않은 경우라면 n-2번째 계단까지의 최댓값을 더해주면 됩니다. 

즉 점화식이 아래와 같이 완성되었습니다.

(case1) S(n) = step[n] + step[n-1] + S(n-3)
(case2) S(n) = step[n] + S(n-2)

 

위 점화식에서 S() 함수는 조건에 맞는 최댓값을 구하는 함수이고, step배열은 계단의 점수를 순서에 맞게 저장해 둔 배열입니다. 

 

이렇게 세운 점화식을 바탕으로 코드를 작성해주었습니다.

우선 res배열에 n까지의 결괏값을 저장해 주어, 재귀함수를 사용할 때 반복적으로 같은 계산을 하지 않도록 해줄 수 있도록 res 배열을 전역변수로 설정해 줍니다. 여기서 res 배열에 동적할당을 하지 않고 전역변수로 설정해 준 이유는 n의 최댓값이 크지 않고, 주어져있으며, 만약 동적 할당을 해줄 경우 0 이하의 값으로 초기화를 해주어야 하기 때문에 전역변수로 설정해서 그 과정을 생략했습니다. 

그리고 S() 함수는 점화식에 따라 작성해 주었습니다. 그전에 조건을 몇 가지 추가했는데, n이 0보다 작으면 해당 계단이 없다는 뜻이기 때문에, 0을 return하여 결괏값에 영향이 없도록 했고, res[n]이 0보다 큰 경우, 즉 이전에 이미 계산을 하여 결괏값이 이미 저장되어 있는 경우에는 별도의 계산 없이 그 값을 return 하도록 하여 계산과정을 줄였습니다. 마지막 조건으로 n이 2보다 작거나 같으면 값이 3번 연속될 일이 없기 때문에, 저장된 step 배열에 있는 n까지의 값을 모두 더해주도록 했습니다. 

이 이후에는 위 점화식에서 작성한 case1의 결괏값을 c1에, case2의 결과값을 c2에 저장하여 더 크기가 큰 쪽을 res 배열에 저장하고 return 하도록 했습니다. 

#include <stdio.h>
#include <stdlib.h>

int res[301];

int S(int n, int *step) {
    if (n < 0) return 0;
    if (res[n] > 0) return res[n];
    
    if (n <= 2) {
        for (int i = 0; i <= n; i++) res[n] += step[i];
        return res[n];
    }
    
    int c1 = step[n-1] + S(n-3, step);
    int c2 = S(n-2, step);
    if (c1 > c2) {
        res[n] = step[n] + c1;
        return res[n];
    } else {
        res[n] = step[n] + c2;
        return res[n];
    }
}

int main() {
    int n;
    scanf("%d", &n);
    
    int *step = (int *)malloc(sizeof(int) * (n+1));
    step[0] = 0;
    for (int i = 1; i <= n; i++) scanf("%d", &step[i]);
    
    printf("%d", S(n, step));
    free(step);
}

 

 

 

이렇게 코드를 작성하여 백준에 제출하면 아래와 같이 정답 처리 되는 것을 볼 수 있습니다. 

 

 

 

추가로 예제입출력이 하나밖에 나와있지 않아 반례를 찾기가 개인적으로 어려워서 질문게시판에서 제 경우에 맞는 반례를 열심히 찾았었는데, 제가 참고한 유용했던 반례 몇 가지 링크를 달아두겠습니다. 

반례1: https://www.acmicpc.net/board/view/130877

글 읽기 - 반례가 없습니다

반례2: https://www.acmicpc.net/board/view/126164\

글 읽기 - 반례 부탁 드립니다.. ㅜ

반례3: 질문 게시판에서 보고 노트에 적어가며 푼 것은 있는데 어디서 봤는지 기억이 나지 않아, 직접 적어서 남깁니다. 개인적으로 해당 반례가 가장 유용하게 사용됐습니다.

Input: 6 40 40 20 1 20 5
Answer: 86