알고리즘 풀이 - 백준 1912(연속합, DP)

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제 링크는 여기를 참조

 

문제의 내용을 보려면 아래 더보기 클릭

 

이 문제는 배열의 연속합 중 가장 큰 값을 구하는 문제이다.

 

 

2. 풀이

 

이 문제는 간단하게 DP로 풀어낼 수 있다.

우선 문제를 이해하자. 배열 내에서 단순히 값을 몇 개 뽑아서 더하는 것이 아니라 연속합 중 최대의 경우를 구해야 한다.
연속합은 1개만 있어도 연속합이 될 수 있다.

아래와 같은 배열이 있을 때를 예시로 조금만 알아보자. arr[i]는 원 배열이고, sum[i]는 연속합이 최대가 되는 경우의 배열이다.

인덱스 i	0	1	2	3
arr[i]	10	-12	30	-8
sum[i]	10	-2	30	22

 

sum[i]을 보며 왜 저렇게 되었는지 알아보자.

index=0일 때, 현재 위치 기준 최대 연속합은 자기 자신 뿐이므로 sum[0] = 10
index=1일 때, 현재 위치 기준 최대 연속합은 자기 자신 보다는 이전과의 합이므로 10+(-12)가 되어 sum[1] = -2
index=2일 때, 현재 위치 기준 최대 연속합은 자기 자신이 이전과의 합보다 크므로 sum[2] = 30
index=3일 때, 현재 위치 기준 최대 연속합은 자기 자신 보다는 이전과의 합이므로 30+(-8)이 되어 sum[3] = 22

 

즉, 현재 위치 기준 최대 연속합은 이전 연속합과 더하거나 더하지 않거나 2가지 중 한 가지가 된다.

 

위를 기반으로 점화식을 만들 수 있으며, 각 부분에서 이전의 결과가 반복적으로 사용되고 해당 최적 결과값이 그대로 사용되니 DP의 두 가지 조건인 Overlapping Subproblems와 Optimal Substructure를 만족한다.

 

그렇다면, DP로 풀 수 있으니 저장할 State의 정의를 한 번 세워보자. 여기서 State는 배열의 길이에 따른 위치 뿐이다. 아래와 같을 것이다. 따라서 1차원으로 저장할 수 있다.

위에서 sum 배열로 썼는데 DP 배열이라고 바꿔서 쓰자.(DP 문제임을 강조하기 위해..)
정의 : DP[N] = 위치 N에서의 연속합의 최대값

 

기저 상태와 점화식을 알아보자.

기저 상태는 첫번째 연속합의 결과를 결정하는 경우일 것이다. 제일 처음은 단순히 그 위치의 원 배열의 숫자가 된다.
기저 상태 : DP[0] = arr[0]

점화식은 이전의 연속합과 합하거나 하지 않거나 이므로 그 중 더 큰 값으로 구한다.
점화식 : DP[N] = Math.max(DP[N-1] + arr[N], arr[N])

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

1) Bottom-up 방식

import java.io.*;

public class Main {
    static int arr[];
    static int dp[];
    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());
        arr = new int[n];
	    dp = new int[n];

        String line[] = br.readLine().split(" ");
        
        // 기저 상태 지정
        dp[0] = Integer.parseInt(line[0]);
        
        // 최대 연속값 미리 지정
        int max_val = dp[0];
        
        for(int i=1; i < n; i++){
            arr[i] = Integer.parseInt(line[i]);
            dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);
            max_val = Math.max(max_val, dp[i]);
        }
        bw.write(String.valueOf(max_val));
        br.close();
        bw.flush();
    }
}

 

2) Top-Down 방식

import java.io.*;

public class Main{
    static int[] arr;
    static int[] dp;
    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());
        String s[] = br.readLine().split(" ");
        
        arr = new int[n];
        dp = new int[n];
        
        for(int i=0; i < n; i++){
            arr[i] = Integer.parseInt(s[i]);
            dp[i] = Integer.MIN_VALUE; // Top-Down에서는 반환 조건을 위해 초기에 최소값으로 지정
            // 문제에서 -1000 ~ 1000까지만 나오고 100,000개 이므로 최소 -1억이다.
            // 이를 기반으로 아래에서 조건식 지정
        }
        
        int max_val = arr[0]; // 최초 최대값은 arr[0]으로 초기화
        dp[0] = arr[0];
        
        topDown(n-1);
        for(int i=1; i < n; i++){
            max_val = Math.max(max_val, dp[i]);
        }
        
        bw.write(String.valueOf(max_val));
        br.close();
        bw.flush();
    }
    
    // Top-Down 방식
    public static int topDown(int n){
        // 여기서 반환 조건식을 지정함
        // 값이 최소값이 아니거나 n=0이면 반환
        if(dp[n] > Integer.MIN_VALUE || n == 0) return dp[n]; // 값이 있거나 n이 0이면 반환
        
        // 재귀를 통해서 값을 구해온다.
        return dp[n] = Math.max(topDown(n-1) + arr[n], arr[n]);
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.