백준 1912번 수열합 _ 동적계획법 DP (C++, python)

문제: https://www.acmicpc.net/problem/1912

1912번: 연속합

이번 문제는 간단한 동적계획법을 이용하여 푸는 수열합 문제입니다!
난이도에 비해서 정답률이 굉장히 낮은 편인데요, 아마도 DP, 동적계획법에 익숙하지 않으신 분들은 쉽게 접근하기 힘들었을 수 있을 것 같아요.

동적계획법은 특별한 알고리즘이 아니에요.
복잡하거나 계산이 까다로운 문제를 작은 부분문제로 나누어보는 것을 말한답니다.
그런데 이는 mergesort처럼 분할정복 알고리즘과도 비슷해보이는데요,
차이점은
분할정복에서는 큰 하나의 문제를 해결하기 위해, 작은 것들로 쪼개고 다시 합치면서 풀어나갔다면,
동적계획법에서는 큰 문제를 해결하기 위해 작은 것들로 쪼개서 풀지만, 그 과정이 계속 반복되어 시간복잡도가 너무 커지는 문제들의 효율적 해결을 위해, 작은 값들이 구해지면 별도로 저장해놓았다가 쓰일 때마다 그 값을 바로 호출하는 (memorization) 메모리제이션 방법이 자주 활용된답니다.

분할정복으로 풀자니 계속 그 과정이 반복되고! 재귀로 풀자니 시간복잡도가 너무 커져버린다면? 동적계획법에 그 해답이 있답니다.
대표적인 문제는 피보나치가 문제가 있겠네요.
간단히 f(n) = f(n-1) + f(n-2)라는 재귀를 이용해 풀면 될 것 같지만 실제로는 아래 그림처럼 매번 불필요하게 같은 함수를 호출하게 되는 걸 볼 수 있습니다.
f(5)를 호출하는데 f(1)이 5번 쓰였는데... f(100000)을 호출한다면 f(1)부터 f(99999)까지 함수들이 중복되어서 얼마나 많이 호출될까요...

피보나치 트리

자, 그럼 이제 본론으로 돌아와서 이번 문제를 볼까요?
n개의 정수로 이루어진 수열에서 이웃 정수들과의 합이 최대가 되면 된다고 하네요.
그럼 동적계획법의 이념을 따라 한번 n이 1부터 보죠.
10 -4 3 1 5 6 -35 12 21 -1 - n이 1개일 땐 그게 최대겠죠. - 10
10 -4 3 1 5 6 -35 12 21 -1 - n이 2개일 땐, 2번째 요소(-4)입장에서는 자기자신(-4)보다 합친 게(6) 낫군요! 그런데 그것보다 10이 더 크네요 - 10
10 -4 3 1 5 6 -35 12 21 -1 - n이 3개일 땐, 3번째 요소 입장(3)에서는 자기자신(3)보다 두번째 요소의 최선(6)과 합친 게(9) 낫네요, 그것보단 10이 큽니다!

규칙성이 보이시나요?
n번째를 검사할 때, (n-1)번째 숫자의 최선과 자신의 합 vs 자기 자신을 비교한 후, 그것과 여태 나온 최댓값과 비교하면 되겠네요!
말로 하니 좀 복잡한데요, 코드로 보면 바로 이해할 겁니다.
먼저 C++ 로 짠 코드입니다.

#include <iostream>
#include <list>
using namespace std;

int main(){
    int num, max;
    cin >> num;
    int array[num], dp[num];
    for (int i=0; i<num; i++) {cin>>array[i];}
    max = dp[0] = array[0]; // 첫번째 요소의 최선은 자기자신
    for (int i=1; i<num; i++)
    {
        if (dp[i-1]+array[i]>array[i]) dp[i]=dp[i-1]+array[i]; // i-1번째 요소의 최선과 합과 비교
        else dp[i] = array[i];
        if (dp[i] > max) max = dp[i]; // 여태 나온 최댓값과 비교
    }
    cout << max;
    return 0;
}

다음은 python으로 짠 코드입니다. 5줄로 끝났네요.
인풋,아웃풋,변수 할당 빼면.. 1줄로도 짤 수 있었던 문제랍니다.
파이썬이 여러모로 간편하긴 하쥬..?

num = int(input())
arr = list(map(int,input().split()))
dp=[arr[0]]
for i in range(1,num): dp.append(dp[i-1]+arr[i]) if (dp[i-1]+arr[i]>arr[i]) else dp.append(arr[i])
print(max(dp))

하지만 메모리와 시간은... 간편한 만큼 trade off가 있네요.

c++ vs python

 

끝!