1912번
-
백준 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..