[백준] 1912번 연속합 _ JAVA ( 주석 설명 )

1번

- 머릿속으로 'dp[] 배열, 메모제이션을 어떻게 할까?' 고민만 하다가 아래 자료를 참고하며 풀었다.

- 연속합 중 최댓값을 찾는 문제이므로,

dp[i] = Math.max(dp[i-1]+ary[i], ary[i]) // i까지의 연속합 vs i 값 => i-1까지의 연속합이 음수이면, i부터 연속합을 구하는 방식

의 점화식을 세울 수 있다.

 

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

[백준] 1912번 : 연속합 - JAVA [자바]

 

→ Top-down 방식

- 유의할 점

dp[] 에 값이 들어가있을 때 불필요한 중복 계산을 막기 위해 바로 return을 해주는데,

여기에서 dp[] 배열을 int로 생성을 하면 '값이 들어가있는지 유무'를 올바르게 할 수가 없어 Integer로 생성을 해주어야 한다.

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

public class Main {
    static int[] ary; //n개의 수열을 입력받을 공간
    static Integer[] dp; //연속합을 저장할 공간 //빈 공간을 체크하기 위해(계산 결과 dp 배열에 0이 들어올 수도 있음) Integer[] 로 선언해줘야 한다.
    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());
        ary = new int[N];
        dp = new Integer[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;++i){
            ary[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = ary[0]; //dp[0]은 첫 원소로 이전에 탐색할 것이 없기 때문에 ary[0]으로 초괴화 해준다.
        max = ary[0]; //max 또한 연속합 최대값의 default 값으로 ary[0]으로 초기화 해준다.

        solve(N-1); //ary[N-1], 마지막 인덱스까지 탐색을 한다.
        System.out.println(max);
    }

    //Top-down 방식
    private static int solve(int N){
        if(dp[N]!=null) //dp[] 인덱스에 이미 정의된 값이 있다면 바로 리턴해준다.
            return dp[N];

        dp[N] = Math.max(ary[N], solve(N-1)+ary[N]); //N까지의 누적합 vs N 값을 비교하여 큰 값을 dp[N] 인덱스에 넣어준다. (ary[N]이 대입된다는 것은 dp[N-1]이 음수였다는 것)
        max = Math.max(dp[N], max); //최대 연속합 또한 바로 갱신해준다. //나중에 dp 배열 완전 탐색함으로 max 값을 찾아도 된다.

        return dp[N];
    }
}

 

 

---

 

2번

→ Bottom-up 방식

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

public class Main {
    static int[] ary; //n개의 수열을 입력받을 공간
    static int[] dp; //연속합을 저장할 공간 //빈 공간을 체크하기 위해(계산 결과 dp 배열에 0이 들어올 수도 있음) Integer[] 로 선언해줘야 한다.
    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());
        ary = new int[N];
        dp = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;++i){
            ary[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = ary[0]; //dp[0]은 첫 원소로 이전에 탐색할 것이 없기 때문에 ary[0]으로 초괴화 해준다.
        max = ary[0]; //max 또한 연속합 최대값의 default 값으로 ary[0]으로 초기화 해준다.

        solve2(N-1); //ary[N-1], 마지막 인덱스까지 탐색을 한다.
        System.out.println(max);
    }

    //Bottom-up 방식
    private static void solve2(int N){
        for(int i=1;i<=N;++i){
            dp[i] = Math.max(dp[i-1]+ary[i], ary[i]); //N까지의 누적합 vs N 값을 비교하여 큰 값을 dp[N] 인덱스에 넣어준다. (ary[N]이 대입된다는 것은 dp[N-1]이 음수였다는 것)
            max = Math.max(dp[i], max); //최대 연속합 또한 바로 갱신해준다. //나중에 dp 배열 완전 탐색함으로 max 값을 찾아도 된다.
        }
    }
}