[백준] 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();
    }
}

---

비슷한 유형의 문제가 나열된다고 해도, 기존 풀이방식의 틀에 갇히지 말자.

 

[참고] https://st-lab.tistory.com/140