[백준 알고리즘] (DP&DC) 1912번 Java 풀이

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 1105

출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]

 

백준 알고리즘 1912번

 

문제를 접하고 바로 저번 학기에 수강했던 알고리즘 수업 내용이 떠올랐고, 대략적으로 풀이 내용이 기억났었는데 구현 방식이 구체적으로 떠오르지 않아 교재였던 Introduction to Algorithms(3rd Edition) - Cormen을 다시 살펴봤다.

교재에서는 DP파트에 들어있지 않고, 이 문제와 동일하지만 조금 더 요구사항이 있는(교재에서는 부분도 함께 출력하라고 함) 문제로 분할정복(Divide&Conquer) 파트에서 다뤄져 있다.

먼저 교재에서는 두 가지 풀이 방법이 제시되어있는데, 1) 주먹구구식 2)분할계획법 풀이이다.
(엄밀히 말하면 주먹구구식 풀이는 그냥 간단하다고 언급만 되어있고 구현은 슈도코드도 안나와있다..)

어쨌든 지금은 공부하는 과정이니까... 그 두 가지 풀이를 모두 풀어보고 한 번 더 DP로도 풀어봤다. 
결과적으로 주먹구구식 풀이는 역시나 메모리초과가 발생하고 나머지 풀이는 정답 결과를 받았다!

 

<첫 번째 풀이(주먹구구식)> - 메모리 초과

package dp;
 
import java.util.Scanner;
 
public class N1912_RuleofThumbs {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt();
        int arr[] = new int[n];
        
        for(int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }
        int max=-9999999;
        int sum[][] = new int[n][n];
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(i>j) {
                    sum[i][j] = -99999999;
                }
                else if(i == j) {
                    sum[i][j] = arr[j];
                }
                else {
                    sum[i][j] = sum[i][j-1]+arr[j];
                }
            }
        }
        for(int i=0; i<n; i++) {
            for(int j=i; j<n; j++) {
                max = Math.max(max, sum[i][j]);
            }
        }
        System.out.println(max);
    }
 
}
 

<두 번째 풀이(분할정복)>

package dp;
 
import java.util.Scanner;
 
public class N1912_DC{
 
    static int arr[];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt();
        arr = new int[n];
        
        for(int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }
        
        int max = MaxPartialCal(0, n-1);
        System.out.println(max);
    }
    
    public static int CrossingCal(int low, int mid, int high) {
        int lmax=-999999;
        int lsum=0;
        for(int i=mid;i>=low;i--) {
            lsum = lsum + arr[i];
            if(lsum > lmax) {
                lmax = lsum;
            }
        }
        int rmax =-999999;
        int rsum =0;
        for(int i=mid+1;i<=high;i++) {
            rsum = rsum + arr[i];
            if(rsum > rmax) {
                rmax = rsum;
            }
        }
        return rmax + lmax;
    }
    
    public static int MaxPartialCal(int low, int high) {
        if(low ==high) {
            return arr[low];  //basecase : only one element 
        }
        else {
            int mid = (low+high)/2;
            int lmax = MaxPartialCal(low, mid);
            int rmax = MaxPartialCal(mid+1,high);
            int cmax = CrossingCal(low,mid,high);
            
            if(lmax >= rmax && lmax>=cmax) {
                return lmax;
            }
            else if(rmax >= lmax && rmax >=cmax){
                return rmax;
            }
            else {
                return cmax;
            }
        }
    }
 
}

<세 번째 풀이(DP)>

package dp;
 
import java.util.Scanner;
 
public class N1912{
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        int arr[] = new int[n];
        int dp[] = new int[n];
        
        for(int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }
        sc.close();
        
        dp[0] = arr[0];
        
        for(int i=1; i<n; i++) {
            dp[i] = Math.max(arr[i], dp[i-1]+arr[i]);
        }
        
        int max = -9999999;
        for(int i=0; i<n; i++) {
            max = Math.max(dp[i], max);
        }
        System.out.println(max);
    }
}