[Java] 백준 1823번 : 수확 (feat: DP의 Bottom-up, Top-down)

문제소개

 

해결과정

DP문제를 풀 때 거의 항상(?) 반복문을 활용한 Bottom-up 방식으로 풀어왔다.

Top-down 방식은 재귀를 활용해 가장 큰 문제를 해결하는데, 익숙치 않아서 기피하게 되었다.

 

다음 포스팅에 소개할 문제가 그렇지만, Top-down 방식으로 풀면 간단하게 풀 수 있는데 Bottom-up 방식으로 시도하면 굉장히 머리가 아파지는 문제가 있기 때문에 두 가지 방식으로 모두 풀이해 Top-down과 Bottom-up, 모두 챙겨보려고 한다.

- Bottom-up

대부분이 그렇듯, 가장 작은 부분 문제부터 큰 부분문제로 어떻게 나아갈지를 고민하고 점화식을 먼저 세운다.

그 뒤, 필요한 초기 dp배열에 값을 지정해준 뒤 반복문을 통해 남은 dp배열을 채워나간다.

 

이 문제에서 점화식은 아래와 같이 설정했다.

dp[i][j] = Math.max(dp[i - 1][j] + map[i] * count, dp[i][j + 1] + map[j] * count);

 

dp[i][j]는 가장 양끝에서 부터 가운데로 오면서 i번째, j번째까지 왔을 때 가장 큰 수확량을 담고있다.

따라서 dp[i][j]로 올 수 있는 두 가지 상황, dp[i-1][j]에서 i번째 작물을 수확한 상황과 dp[i][j+1]에서 j번째 작물을 수확한 상황 중, 수확량의 총량이 더 큰 쪽이 dp[i][j]가 된다.

 

이를 반복문을 통해 모든 dp배열을 완성하면 되고, dp배열 중 가장 큰 값을 찾으면 정답이 된다.

 

추가로 이러한 Bottom-up 방식을 사용할 때는 dp배열의 일부를 적당한 값으로 초기화시켜주는 것이 중요하다.

현재 상황에서는 작물의 번호가 1~N까지 있다고 했을 때, 가장 좌측의 0번째와 나머지 작물에 대한 dp배열값과 가장 우측의 N+1번째와 나머지 작물들에 대한 dp배열값을 초기화시켜줬다.

package DP.백준1823_수확;

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

public class Main {

    static int[] map;
    static int N;
    static int[][] dp;
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N + 1];
        dp = new int[N + 2][N + 2];
        Arrays.stream(dp)
                .forEach(arr -> Arrays.fill(arr, -1));

        for (int i = 1; i <= N; i++) {
            map[i] = Integer.parseInt(br.readLine());
        }

        dp[0][N+1] = 0;
        for (int i = 1; i <= N; i++) {
            dp[i][N+1] = dp[i-1][N+1] + map[i] * i;
        }

        for (int i = N; i >= 1; i--) {
            dp[0][i] = dp[0][i+1] + map[i] * (N - i + 1);
        }

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

        int result = Arrays.stream(dp)
                .flatMapToInt(arr -> Arrays.stream(arr))
                .max()
                .orElse(-1);

        System.out.println(result);

    }
}

 

 

- Top-down

Top-down으로 이 문제를 접근할 때는 Bottom-up과 dp배열에 담는 내용이 다르다.

dp[i][j]란, 가장 안쪽에서부터 i, j번까지 밖으로 나왔을 때 현재까지의 수확량의 최댓값을 담고있다.

이는 재귀적인 방식으로 구현할 수 있다.

 

안쪽에서 바깥쪽으로 오기때문에, 아래와같은 점화식을 얻을 수 있다.

dp[start][end] = Math.max(findMax(start+1, end, count+1) + count * map[start],
                findMax(start, end-1, count+1) + count * map[end]);

 

항상 큰 틀을 보면서 재귀적인 점화식을 세우는 것에 익숙해지자!

점화식을 세운 뒤,

1. 재귀함수의 종료 조건

2. 이미 계산 처리된 dp배열에 다시 접근했을 때 계산 결과만 다시 반환해주는 조건

위 두 가지만 처리해주면 재귀함수는 완성된다. 아래는 전체 코드이다.

package DP.백준1823_수확;

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

public class Main {

    static int[] map;
    static int N;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N+1];
        dp = new int[N + 2][N + 2];
        Arrays.stream(dp)
                .forEach(arr -> Arrays.fill(arr, -1));

        for (int i = 1; i <= N; i++) {
            map[i] = Integer.parseInt(br.readLine());
        }

        System.out.println(findMax(1, N, 1));
    }

    static int findMax(int start, int end, int count) {
        if (start == end) {
            return count * map[start];
        }
        if (dp[start][end] != -1) {
            return dp[start][end];
        }
        dp[start][end] = Math.max(findMax(start+1, end, count+1) + count * map[start],
                findMax(start, end-1, count+1) + count * map[end]);
        return dp[start][end];
    }
}