• 백준 1912번 연속합 [DP] :: 마이구미
    알고리즘 풀이/동적계획법 2017. 1. 15. 23:50
    반응형

    이번 글은 백준 알고리즘 1912번 문제 "연속합" 을 다뤄본다.

    일단 문제를 보자.

    n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다.

    예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

    문제는 쉽게 이해할 수 있다.

    연속되는 수들을 골라 최대의 합이 되는 수를 고르면 된다.


    사이트에서 알고리즘 분류를 보면 알다시피 동적계획법으로 풀기를 권장하는 문제이다.


    알고리즘 분류

    어떻게 점화식을 만들 수 있을까?

    점화식에 앞서 함정만 파악하면 쉽게 문제를 풀 수 있다.


    임의의 수열 7 8 -9 10 주어졌을 때, 최대의 합은 얼마일까?

    정답은 7과 8을 연속으로 선택함으로써, 15라고 생각하면 문제의 함정에 빠지는 것이다.

    7,8,-9,10 연속된 수를 전부 선택한다면 합은 16이 된다.

    즉, 음수를 선택하더라도 합이 더 큰 경우가 나올 수 있다는 얘기이다.


    조금 더 생각해보면, 이 문제의 해결법을 쉽게 파악할 수 있다.

    연속된 수를 선택하면서 합을 구하는 것이므로, 쉽게 점화식을 찾을 수 있다.


    dp[n] = dp[n] + dp[n-1]

    n번째 이전의 합과 n번째 수를 더하면 n번째까지의 합이 나오므로 위와 같은 점화식을 도출할 수 있다.

    그리고 2가지만 염두하면 된다.

    1. dp[i-1] > 0

      - 이전의 합이 음수라면 선택할 필요 없이 현재부터 다시 선택해나가면 된다. 

    2. dp[i] + dp[i-1] > 0

      - 이전의 합과 현재의 수를 더한 값이 음수라면 선택할 필요가 없다. 


    for(int i=2;i<=n;i++) {

    if (dp[i-1] > 0 && dp[i] + dp[i-1] > 0) { dp[i] += dp[i-1]; } if (max < dp[i]) { max = dp[i]; } }


    하나의 반복문으로도 문제를 해결할 수 있다.

    더 이해를 돕기 위해 Github 사이트를 통해 전체 소스를 확인하길바란다.

    이만 안녕.


    백준 알고리즘 사이트 1912번 연속합 문제

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


    백준 1912번 연속합 전체 소스

    https://github.com/hotehrud/acmicpc/blob/master/algorithm/dp/1912.java




    반응형

    댓글

Designed by Tistory.