백준_연속합(1912) In Java

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

1912번: 연속합

 

풀이

- 처음 문제를 읽었을 때 오름차순으로 정렬 후 양수인 수를 전부더하면 된다고 생각했는데, 문제는 배열에 손을 대지 않고 연속적인 숫자 합을 구하는 문제이다

- dp 배열에는 ar[i] 까지 배열에서의 총합중 최대값이 들어있는 배열이 dp[i] 가 된다.

- 다이나믹 프로그래밍으로서 Top-Down 방법, Bottom-Up 방식이 있다

 

Top-Down

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

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


        recur(N-1);
        System.out.println(max);
    }

    static int recur(int N){
        if(dp[N]==null){
            dp[N]=Math.max(recur(N-1)+ar[N],ar[N]);
            max=Math.max(dp[N],max);
        }
        return dp[N];
    }
}

Bottom-Up

import java.io.BufferedReader;
import java.io.IOException;
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[] ar=new int[N];
        int[] dp=new int[N];
        StringTokenizer st=new StringTokenizer(br.readLine()," ");
        for (int i = 0; i < N; i++) {
            ar[i] = Integer.parseInt(st.nextToken());
        }
        dp[0] = ar[0];
        int max=ar[0];

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

        System.out.println(max);

    }
}

 

성능

첫번째 : Top-Down, 두번째 : Bottom-Up

Top-Down 방식은 재귀를 이용하여 함수를 호출할 떄마다 오버헤드가 발생하여 Bottom-Up 방식이 시간 이나 메모리 측면에서 좀 더 효율적이다.

 

동적프로그래밍 문제는 문제를 생각해보고 직접 확인해보면서 점화식을 세우는 것이 제일 중요한거같다.