[백준 1912번] 연속합 - DP

백준 1912번 동적 계획법(Dynamic Programming)으로 풀 수 있는 문제이다.

1912번: 연속합

 

먼저 문제를 보고 시작하면,

n개의 정수로 이루어진 수열을 입력으로 받는다. 그리고 이 중 몇 개의 수를 선택해서 모두 더한다. 이 중 가장 크게 나올 수 있는 수를 찾는 문제이다. 
여기서 주어진 조건은 꼭 연속된 수를 선택하여야한다.

여기서 처음 문제를 풀 때,

실수를 하였던 부분은 N개의 숫자를 연속으로 선택해서 합이 가장 큰 수를 선택하여야하기 때문에 모든 경우의 수를 더하는 방법을 썼다.

 

즉, 1개~N개를 고를 때의 모든 합을 구해서 가장 큰 수를 저장하고 출력하게 해주었다.

답은 맞았지만 시간초과가 나서 실패했던 방법이다.

 

밑의 소스코드과 같이 짰고

public class BAEKJOON1912 {
    static int N;
    static int[] numbers;
    static int max = -1001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        String[] input =  br.readLine().split(" ");
        numbers = new int[N];

        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(input[i]);
        }

        for (int i = 1; i < N; i++) {
            dp(i);
        }

        System.out.println(max);
    }

    static void dp(int count) {
        for (int i = 0; i < N; i++) {
            int tempT = 0;
            if (i+count >= N) { continue; }
            for(int j = i; j < count+i; j++) {
                tempT += numbers[j];
            }
            if (tempT > max) { max = tempT; }
        }
    }
}

 

다음과 같이 접근할 시 O(N^3)의 시간 복잡도로 계산하게 되었고, 시간초과가 났다.

 

그렇기에 방법을 다시 생각해야했고, DP을 이용한 방법을 생각하게 되었다.

 

첫번째의 조건은,

지금까지 더한 숫자를 더한 DP 배열을 두고 현재 순열의 숫자와 크기를 비교하는 것이다.

즉, 지금까지 숫자를 더한 것이 현재의 숫자보다 작으면 활용할 필요가 없기 때문에 과감히 버리면된다.

dp[i] = Math.max(dp[i-1] + numbers[i], numbers[i]);

 

 

두번째 조건은,

지금까지 더한 숫자와 가장 큰 값을 비교해서 최종 값으로 선택하여주면 된다.

max = Math.max(dp[i], max);

 

이렇게 문제를 해결하게 되면 결국 O(N)의 복잡도로 문제를 빠르게 해결할 수 있다.

 

이전의 방법과 비교해서 훨씬 빠른 속도였고, 여기서 핵심은 지금까지 더한 숫자가 현재의 값보다 작으면 과감히 버리면 된다는 점이었다.

 

전체 소스코드 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BAEKJOON1912 {
    static int N;
    static int[] numbers;
    static int max = -1001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        String[] input = br.readLine().split(" ");
        numbers = new int[N];

        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(input[i]);
        }

        int[] dp = new int[N];
        dp[0] = numbers[0];
        max = numbers[0];

        for(int i = 1; i < N; i++) {
            dp[i] = Math.max(dp[i-1] + numbers[i], numbers[i]);
            max = Math.max(dp[i], max);
        }


        System.out.println(max);
    }
}