[백준] 1912 연속합 - DP(동적계획법) + 분할정복(DivideAndConquer) JAVA

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

1912번: 연속합

코드설명

DP 문제입니다.

 

이 문제는 연속된 몇개의 수를 선택하여 구할 수 있는 합 중 가장 큰 합을 구하는 문제입니다.

( 처음에 단순히 음수가 나왔을때 종료하게하여 틀렷었습니다. )

 

문제 로직은

현재 숫자를 선택했을때 ( 그전까지의 최대합 + 현재숫자 ) > (현재숫자) 일경우 

dp[now] = ( 그전까지의 최대합 + 현재숫자 ) ; 

만약 ( 그전까지의 최대합 + 현재숫자 ) < (현재숫자) 일경우 

dp[now] = ( 현재숫자 );  

 

위의 식을 표현해보면

 

dp[N] : 한 인덱스당 연속된 몇개의 수를 선택햇을때 최대의 합

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

입니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main {
	public static int T, N, M;
	public static int answer = 0;
	public static int[] arr;
	public static int[] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N];
    	dp = new int[N];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	dp[0] = arr[0];
    	answer = dp[0];
    	for(int i=1;i<N;i++) {
    		dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);
    		answer = Math.max(answer, dp[i]);
    	}
    	
    	System.out.println(answer);
    }
    
}

 

 

메모이제이션을 활용한 코드입니다.

package Main;

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

public class Main {
    public static int N;
    public static int[] arr;
    public static int[] memo;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        
        arr = new int[N];
        memo = new int[N];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // 메모 배열을 초기화합니다.
        Arrays.fill(memo, Integer.MIN_VALUE);
        
        int answer = Integer.MIN_VALUE;
        for(int i = 0; i < N; i++) {
            answer = Math.max(answer, maxSubSum(i));
        }
        
        System.out.println(answer);
    }
    
    // i번째 원소를 마지막으로 하는 최대 부분합을 계산하는 재귀 함수
    public static int maxSubSum(int i) {
        // 기저 사례: 첫 번째 원소
        if(i == 0) {
            return arr[0];
        }
        
        // 메모이제이션: 이미 계산된 값이 있으면 그 값을 반환
        if(memo[i] != Integer.MIN_VALUE) {
            return memo[i];
        }
        
        // i번째 원소를 포함하는 경우와 포함하지 않는 경우 중 큰 값을 선택
        memo[i] = Math.max(maxSubSum(i-1) + arr[i], arr[i]);
        
        return memo[i];
    }
}

 

 

분할정복으로 풀이한 코드입니다. 시간초과가 안날것이라고 생각했으나, 시간초과가 발생합니다.

시간복잡도는 n log (n) 으로써 n이 최대 10^5 이 들어온다고 하더라도, 10^5 * 17 = 10^6 * 7 입니다.

그래서 1초 안에 해결된다고 생각했는데, 시간초과가 발생합니다. 아마 재귀호출 과정에서 함수가 호출되는 과정에서 스택에 저장되어서 그런 것 같습니다..

 

또한, 가운데값을 처리할떄, 0부터 hi 까지 모두 돌리면서 Math.max() 를 처리하는데, 이떄 해당 최대값이 나온다면 모두 더한다는 의미로 생각하면 됩니다. 이 부분이 가장 맹점이었습니다. 

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = 0;
	private static int[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		System.out.println(divideAndConquer(arr, 0, N-1));
	}
	
	
	//1. 분할정복을 이용한 풀이
	private static int divideAndConquer(int[] A, int lo, int hi) {
		if(lo == hi) {
			return A[lo];
		}
		
		int ret = 0;
		int mid = ( lo + hi ) / 2;
		int leftSum = divideAndConquer(A, lo, mid);
		int rightSum = divideAndConquer(A, mid + 1, hi);
		
		//중간에 겹치는 부분입니다.
		int midLeftSum = Integer.MIN_VALUE;
		int midRightSum = Integer.MIN_VALUE;
		int midTempSum = 0;
		for(int i = mid; i>=0; i--) {
			midTempSum += arr[i];
			midLeftSum = Math.max(midLeftSum, midTempSum);
		}
		midTempSum = 0;
		for(int i=mid + 1; i<N; i++) {
			midTempSum += arr[i];
			midRightSum = Math.max(midRightSum, midTempSum);
		}
		
		ret = midLeftSum + midRightSum;
		
		ret = Math.max(ret, Math.max(leftSum, rightSum));
		return ret;
	}
	
}