[BOJ/JAVA] 백준 1912번 연속합 ( DP )

 

✔ 문제

난이도 : 실버2 🥈

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

1912번: 연속합

 

 

 

✔ 문제 풀이

입력값의 범위가 n(1 ≤ n ≤ 100,000)이기 때문에 단순히 이중 for문을 통해 계산하게 되면 시간초과가 됩니다.

동적 계획법(DP)을 적용하여 시간복잡도를 낮추어 풀어야합니다.

 

위 문제에서는 '연속되는 몇 개의 수'라는 조건이 주어졌기 때문에 연속되는 수의 누적합을 배열에 저장하여 비교하면서 중복되는 연산을 줄일 수 있습니다.

 

Bottom-Up과 Top-Down 접근방식을 통해 문제를 풀어보겠습니다.

 

💡 Bottom-Up 접근

dp[0] = seq[0];
int max = seq[0];

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

 

sequence는 문제에서 주어진 수열입니다.

dp는 메모이제이션 하기 위한 배열입니다.

 

연속된 수 이기 때문에 이전 값과 현재 값을 더한 수를 알아야 합니다. ( dp[i - 1] + seq[i] )

그렇기 때문에 초기에 dp[0] = seq[0] 을 통해 첫 번째 값을 세팅해 줍니다.

 

그리고 연속된 수가 더 크다면 더한 값을 dp배열에 저장함으로써 다음 연산 시 이전 값만 계산하도록 하여 중복된 연산을 줄일 수 있습니다.

반대로 비교하는 수가 더 크다면 비교하는 수를 dp배열에 입력합니다.

이는 가장 큰 값을 구해야 하기 때문에 연속해서 더한 값이 더 작음으로 새로 연산을 시작하기 위해 비교하는 수를 그대로 입력합니다.

 

 

🔎 전체 코드 ( Bottom-Up 배열 )

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

public class Main{
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
        
        
        int n = Integer.parseInt(br.readLine());
        int[] seq = new int[n];
        int[] dp = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for( int i = 0; i<n; i++){
            seq[i] = Integer.parseInt(st.nextToken());
        }
        
        dp[0] = seq[0];
        int max = seq[0];

        for( int i = 1; i<n; i++){
            dp[i] = Math.max(dp[i-1] + seq[i], seq[i]);
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);

        br.close();
	}
}

 

 

 

💡 Top-Down 접근

static int recur(int n){

    if( dp[n] == null ){
        dp[n] = Math.max(recur(n - 1) + arr[n], arr[n]);

        max = Math.max(max, dp[n]);
    }

    return dp[n];
}

 

배열을 사용한 접근과 마찬가지로 연속한 수의 합과, 연속하지 않았을 때의 수를 비교하여 더 큰 수를 dp배열에 입력하여 중복된 연산을 줄입니다.

 

recur( n ) 을 시작으로 if( dp[n] == null ) 조건을 통해 먼저 세팅된 dp[0] 이 return되면서

bottom-up방식 과 같은 방법으로 dp배열이 하나씩 채워집니다.

 

 

🔎 전체 코드 ( Top-Down 재귀 )

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

public class Main{
    static int[] seq;
    static Integer[] dp;
    static int max;
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        seq = new int[n];
        dp = new Integer[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for( int i = 0; i<n; i++){
            seq[i] = Integer.parseInt(st.nextToken());
        }
        
        dp[0] = seq[0];
        max = seq[0];
        
        recur(n-1);

        System.out.println(max);

        br.close();
	}
    
    static int recur( int n ){
        if( dp[n] == null){
            dp[n] = Math.max(recur(n-1)+seq[n], seq[n]);
            max = Math.max(max, dp[n]);
        }
        
        return dp[n];
    }
}

 

 

 

---

 

 

📚 Reference : https://st-lab.tistory.com/140