백준 연속합 1912

2020-10-27

DP, 구현, 백준, 알고리즘

1. 백준 연속합 1912 문제

1.1. 문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

1.2. 입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

1.3. 출력

첫째 줄에 답을 출력한다.

1.4. 예제 입력 1

10
10 -4 3 1 5 6 -35 12 21 -1

1.5. 예제 출력 1

1.6. 예제 입력 2

10
2 1 -4 3 4 -4 6 5 -5 1

1.7. 예제 출력 2

1.8. 예제 입력 3

5
-1 -2 -3 -4 -5

1.9. 예제 출력 3

-1

1.1. 컴퓨팅적 사고

연속합 문제를 풀때 맨 처음에 생각한 방법은 DFS로 각각의 경우를 모두 구해서 합을 구하는 방식으로 구현하였습니다.
하지만, 4%쯤 되서 시간초과가 발생하는 불상사가 생기게 되었습니다. 문제를 다시 읽어보니 N의 제한이 n(1 ≤ n ≤ 100,000) 까지 였기때문에 1초에 10억번연산을 수행해야하는 경우가 생길 수 있다고 판단하였습니다.

따라서, DFS로 구현하기에는 복잡도 면에서 무리가 있다고 생각하여 메모이제이션(DP)를 이용하였습니다.

테스트 케이스를 잘 살펴보면 이전의 합이 음수일때는 가장 큰값을 구할 수가 없습니다. 그리고, (이전의 합 + 현재의 합)이 음수일 경우도 최댓값을 구할 수가 없습니다.

따라서, 이것을 DP의 조건으로 생각하여 진행하였습니다.

입력

1
2
3

for(int i=0; i<n; i++){
    dp[i] = Integer.parseInt(st.nextToken());
}

맨 처음의 최댓값을 dp[0]으로 기준을 잡고 bottom-up방식으로 구현을 진행하였습니다.

DP 조건

1
2
3

if(dp[i] + dp[i-1] > 0 && dp[i-1] > 0){
    dp[i] = dp[i-1] + dp[i];
}

DP의 조건을 살펴보면 두가지로 나눌 수 있습니다.

처음 이전의 합이 음수라면 선택하지 않고 현재부터 다시 선택합니다. 즉, 이전의 합이 양수일때만 진행한다는 뜻입니다.
이전의 합과 현재의 수를 더한 값이 음수라면 선택하지 않습니다.

최댓값 선택

만약 max값이 dp값보다 작을 경우 현재의 합을 max값으로 갱신시켜줍니다.

1
2
3

if(max < dp[i]){
    max = dp[i];
}

1.2. 소스코드

시간초과 브루트포스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class 연속합1912 {
    static int[] arr;
    static int[] check;
    static int n;
    static ArrayList<Integer> answer;
    static int max = -1000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        check = new int[n];
        answer = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<n; i++){
            dfs(i,1);
        }
        System.out.println(max);
    }

    private static void dfs(int idx, int cnt) {
        if(cnt >= n || idx >= n){
            return;
        }
        int ans = 0;
        for(int i=idx; i<cnt; i++){
            ans += arr[i];
        }
        if(ans != 0){
            if(ans > max){
                max = ans;
            }
        }
        dfs(idx,cnt+1);
        dfs(idx+1,cnt);
    }
}

DP

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class 연속합1912DP {
    static int[] dp;
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<n; i++){
            dp[i] = Integer.parseInt(st.nextToken());
        }

        int max = dp[0];
        for(int i=1; i<n; i++){
            if(dp[i] + dp[i-1] > 0 && dp[i-1] > 0){
                dp[i] = dp[i-1] + dp[i];
            }
            if(max < dp[i]){
                max = dp[i];
            }
        }
         /*
        첫번째 경우 dp[i-1] > 0
          이전의 합이 음수라면 선택하지 않습니다.
        두번째 경우 dp[i] + dp[i-1] > 0
          이전의 합과 현재의 수를 더한 값이 음수라면 선택하지 않습니다.
         */
        System.out.println(max);

    }
}

AlgorithmBOJ