[백준] DP - 1912번, 연속합
* 공부 목표
DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052
문) 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. 처음 접근 방식 ❌
d[i] = arr[i];
if(arr[i] < d[i-1]+arr[i] && d[i-1] < d[i-1]+arr[i]) {
d[i] = d[i-1]+arr[i];
} else if(arr[i] > d[i-1]+arr[i]) d[i] = arr[i];dp에 저장할 수 있는 경우가 다음 두 조건을 모두 만족할 때라고 생각했음.
1) 현재의 값 < 이전 dp값 + 현재 값
2) 이전 dp값 < 이전 dp값 + 현재 값
반례, 해당 논리는 3+4+(-4)+6+5 의 축적값을 무시하게 된다.
10
2 1 -4 3 4 -4 6 5 -5 1
분명히 (이전 dp값 + 현재 값)이 현재 값보다 클 때 저장하는 것은 맞고,
음수 때문에 2번째 조건을 달았는데 오히려 답이 이상하게 나왔다.
도저히 답을 못 찾고 헤매다 결국 다른 풀이를 참고하게 됐다.
2. 다른 풀이 ✅
음수와 양수 상관없이 <연속적으로 선택한 수의 합>이 최대가 되게 하려면,
(이전까지의 누적합(dp) + 현재 값) 과 현재 값을 비교하여 최댓값을 현 dp에 저장하면 된다.
for (int i = 1; i < N; i++) {
dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
}
현재 값이 (이전 dp+현재값)보다 클 수 있다는 것과 Math라이브러리를 활용하여 간편하게 작성할 생각을 못했다.
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main{
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
int[] d = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i=0; i<n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
d[0] = arr[0];
for(int i=1; i<n; i++) {
d[i] = Math.max(arr[i], d[i-1]+arr[i]);
}
int max = arr[0];
for(int i=0; i<n; i++) {
max = d[i]>max? d[i] : max;
}
bw.write(String.valueOf(max));
br.close();
bw.flush();
bw.close();
}
}비슷한 유형의 문제가 나열된다고 해도, 기존 풀이방식의 틀에 갇히지 말자.