[java 백준] 실버 2/1912번 연속합

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

import java.util.Scanner;
 
public class Main {
 
    public static int n;
 
    public static int[] arr;
    public static int[] dp;
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n + 3];
        dp = new int[n + 3];
 
        for (int i = 1; i <= n; i++) {
 
            arr[i] = sc.nextInt();
 
        }
        dp[1] = arr[1];
 
        for (int i = 2; i <= n; i++) {
            if (dp[i - 1] + arr[i] >= arr[i]) {
                dp[i] = dp[i - 1] + arr[i];
            } else if (dp[i - 1] + arr[i] < arr[i]) {
                dp[i] = arr[i];
            }
        }
 
        int max = dp[1];
        for (int i = 1; i <= n; i++) {
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        System.out.println(max);
 
    }
 
}

dp는 누적합을 이용해야한다는 것을 기억해야한다! 

처음에는 계산을 여러번하는 방법으로 생각했는데, 그러면 매우 비효율적이고 dp 의도대로 푸는게 아니게된다. 

아래 링크로 걸어둔 사이트에서 생각하는 방법의 힌트를 찾아서 문제를 풀어봤다. 

 

n=5이고 숫자가 2,1,-4,3,4가 있다고 해보자. 

dp[1]=2

d[2]의 경우, arr[2]<dp[1]+arr[2]이므로, dp[2]=3이다.

dp[3]의 경우, arr[3]<arr[3]+dp[2] 즉 -4<-1이므로 dp[3]=-1이다

dp[4]의 경우 arr[4]>dp[3]+arr[4] 즉 3>2이기 때문에 dp[4]=3이 된다.

--> dp[4]같은 경우 때문에 

 else if (dp[i - 1] + arr[i] < arr[i]) {

                dp[i] = arr[i];

            }

else if 코드가 필요한 것이다. 그동안의 연속합이 현재 값보다 작으면 현재값부터 연속합으로 시작하는게 더 큰 값이 되기 때문이다. (--> 나는 이걸 생각하지 못했다ㅜㅜ)

dp[5]의 경우 arr[5]<dp[4[+arr[5] 즉 4<7이기 때문에 dp[5]=7이 된다.

 

2,3,-1,3,7 중에 가장 큰 값은 7이기 때문에 답은 7이 된다. 

 

 

참고한 사이트

---

https://zoonvivor.tistory.com/152

Zoonvivor

 

내가 놓친 부분

---

dp를 풀다보면 무조건 최대값 만들기에만 몰두해서 정작 누적합을 통한 규칙만들기를 놓친다. 

 

예를 들어 n이 3이고 2,1,-4가 있을 때

dp[1]=2

dp[2]=3

dp[3]=-1이다

 

이럴 경우 max를 구하는 코드를 통해 2,3,-1중 최대값인 3을 구할 수 있다.

 

하지만 나는 3을 찾기에만 몰두해서 (2+1) ,(1+-4),(2+1,+-4) 계산을 다 하는 바람에 3번이나 계산해버렸다. 누적합을 이용해서 dp[1]~dp[3]까지 구하고,  max 구하는 식을 통해 한번에 탐색할 수 있는 것이였다.  아직 연습이 더 필요할 것 같다...ㅜ