-
백준 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
반응형'알고리즘 풀이 > 동적계획법' 카테고리의 다른 글
백준 3745번 오름세 [LIS] :: 마이구미 (0) 2017.02.17 백준 2579번 계단 오르기 [DP] :: 마이구미 (4) 2017.01.16 백준 2156번 포도주 시식 [DP] :: 마이구미 (5) 2017.01.16 백준 1932번 숫자삼각형 [DP] :: 마이구미 (0) 2017.01.03 백준 2688번 줄어들지 않아 [DP] :: 마이구미 (0) 2017.01.02