[백준 1912번/C언어] 연속합, 동적계획법으로 풀기

백준 1912번 문제를 Dynamic Programming(DP, 동적계획법)으로 풀어보았습니다. 

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

1912번: 연속합

 

 

 

문제 내용은 아래와 같습니다. 

 

목표했던 문제가 있어 동적계획법 공부를 시작하였는데, 목표했던 문제는 이미 해결했으나, 한 번 공부를 시작한 만큼 다른 문제들도 풀어보고 싶어서 이 문제를 골랐습니다. 동적계획법을 공부하고 싶으신 분들은 제 블로그에 관련된 문제를 푼 게시글이 있으니 참고해 주시기 바랍니다. 동적계획법은 많이 접해보고, 나중에는 해당 문제가 동적계획법인지 모르고 접해도 점화식을 통해 풀어야겠다는 판단이 서는 것이 중요하다고 합니다. 따라서 저는 이번 기회에 동적계획법으로 풀 수 있는 예제를 최대한 많이 접해보려고 합니다. 

 

 

이 문제를 풀 때, 저는 한 번의 실패를 겪은 후에 올바른 점화식을 찾을 수 있었는데요, 해당 접근법이 왜 틀렸는지와 올바른 접근법으로 어떻게 도달했는지를 기록해보려 합니다. 

처음에 제가 실패한 이유는 아래 반례를 생각하지 못해서입니다.

30
2 -3 10 -6 -2 -4 -5 3 -9 3 8 -6 -6 4 6 -7 5 -7 3 4 10 0 -3 -6 6 -9 -7 -10 0 -2

정답 18

 

반례에서 빨간색으로 밑줄 친 부분을 모두 더해야 답인 18이 도출됩니다. 하지만 제 첫 코드는 3 앞에 -7과 그 앞에 5를 더했을 때 -2라는 음수가 발생하기 때문에 더하면 오히려 값이 작아진다고 생각하여 3+4+10까지만 더한 17을 도출했습니다. 하지만 더 앞으로 가서 -7+5-7+6+4까지 하면 1이라는 양수가 나오기 때문에 더해야 하는 것이 맞는 판단이기 때문에 제 첫 코드가 실패했습니다. 

 

따라서 저는 다시 처음으로 돌아가서 n=1일때부터 차근히 생각하며 다시 점화식을 떠올리려고 했습니다. 그렇게 떠올린 점화식은 다음과 같습니다. 

F(n) = F(n-1) + nums[n]  (F(n-1) > 0)
        = nums[n]                (F(n-1) <= 0)

 

즉, 자신 이전까지의 결괏값이 0보다 크면 이전 결괏값에 자기 자신 차례의 숫자를 더하고, 0보다 작으면 그냥 자기 자신이 결괏값이 되는 것입니다. 이렇게 한 후 F(n)의 최댓값을 찾으면, 그 값이 바로 최종 결괏값이 됩니다. 

 

 

위 점화식을 바탕으로 구현한 코드는 다음과 같습니다. 

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

int main() {
    int n;
    scanf("%d", &n);
    
    int *nums = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) scanf("%d", &nums[i]);
    
    int *res = (int *)malloc(sizeof(int) * n);
    res[0] = nums[0];
    for (int i = 1; i < n; i++) {
        if (res[i-1] < 0) res[i] = nums[i];
        else res[i] = res[i-1] + nums[i];
    }
    
    int max = -1000;
    for (int i = 0; i < n; i++) {
        if (res[i] > max) max = res[i];
    }
    printf("%d", max);
    
    free(nums);
    free(res);
}