[BOJ][C++] 백준 1912번 연속합
Updated:
1912번 연속합
1. 문제 정보
백준 온라인 저지 [1912번 연속합] 문제의 링크입니다.
문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
예제 입력1
10
10 -4 3 1 5 6 -35 12 21 -1
예제 출력1
33
예제 입력2
10
2 1 -4 3 4 -4 6 5 -5 1
예제 출력2
14
예제 입력3
5
-1 -2 -3 -4 -5
예제 출력3
-1
시간 / 메모리 제한
1초 / 128MB
2. 생각
-
수열 중 연속된 부분 수열의 합이 최대가 되는 값을 구하는 문제입니다.
- dp[i]를 i번째 수로 끝나는 수열의 합으로 정의하겠습니다. 그렇다면 두 가지의 경우가 생깁니다.
- i번째 수가 포함되는 경우
- i번째 수가 포함되지 않는 경우
위의 경우에서
1)의 경우에는 i번째 수를 더할 것이고,
2)의 경우에는 i번째 수가 그 자체로 연속된 부분 수열의 시작을 의미합니다. - 위의 경우를 점화식으로 나타내면 i번째 입력값을 a[i]라고 했을 때,
- dp[i] = a[i] + dp[i]
- dp[i] = a[i] 입니다.
- 저는 배열의 최대값을 구하는 데에
헤더에 있는 max_element 함수를 사용했습니다. 구하는 과정에서 저는 dp[0]의 값을 0으로 초기화했기 때문에 예제 3번과 같은 dp[0]의 값보다 작은 테스트케이스에서 틀리지 않도록 max_element 함수에서 검색 값을 1번 인덱스로 두었습니다. ((dp[1]~dp[n])까지 검색)
- 참고
ex1) 예제 1
i dp[i] + a[i] a[i] 최종값(dp[i]) 1 0 + 10 = 10 10 10 2 10 + (-4) = 6 -4 6 3 6 + 3 = 9 3 3 4 9 + 1 = 10 1 10 5 10 + 5 = 15 5 15 6 15 + 6 = 21 6 21 7 21 + (-35) = -14 -35 -14 8 -14 + 12 = -2 12 12 9 12 + 21 = 33 21 33 10 33 + (-1) = 32 -1 32 최종적으로 최대값은 a[8] 과 a[9] 를 더한 33 입니다.
ex1) 예제 1
i 1 2 3 4 5 6 7 8 9 10 a[i] 10 -4 3 1 5 6 -35 12 21 -1 dp 10 6 9 10 15 21 -14 12 33 32 ex2) 예제 2
i 1 2 3 4 5 6 7 8 9 10 a[i] 2 1 -4 3 4 -4 6 5 -5 1 dp 2 3 -1 3 7 3 9 14 9 10 ex3) 예제 3
i 1 2 3 4 5 a[i] -1 -2 -3 -4 -5 dp -1 -2 -3 -4 -5
3. 소스코드 (C++)
