2240 - 자두나무

문제: boj.kr/2240
날짜: 09/20 (금)
성공여부: X [02:20:01]

 

자두 나무에서 떨어지는 자두를 최대 W만큼 움직여 최대한 많은 자두를 먹는 문제이다.

 

완전 탐색

자두 나무는 각각 2개의 위치에 있고, 시간 별로 둘 중 하나의 나무에서 자두가 떨어진다. 가장 간단하게 생각해볼 수 있는 방법은 역시 완전 탐색이다.

 

여기서 주어지는 변수를 생각해보면 시간, 이동 횟수, 위치가 있다. 자두가 처음에 1 위치에서 시작하니까 해당 위치를 기준으로 이동 횟수를 소모하지 않고 제자리에 있느냐 혹은 이동 횟수를 소모해서 1 위치로 이동하느냐 두 가지 경우의 수가 있다. 그럼 다음과 같이 두 번의 호출이 필요함을 예상할 수 있다.

go(t + 1, w, 0);

go(t + 1, w-1, 1);

 

하나의 위치에서 시간의 흐름에 따라 2가지의 갈래로 나뉘니까 해당 로직의 시간 복잡도는 최소 2^30 임을 알 수 있다. 왜냐면 w가 최대 30이기 때문이다. 움직이지 않는 경우의 수로만 보면 T의 최대인 1000까지도 가능하다. 2^30(약 10억)만 해도 이미 너무 큰 수이기 때문에 완전 탐색으로는 불가능하다는 것을 알 수 있다.

 

그래서 시간을 줄일 방법이 없을까해서 직접 완전 탐색의 흐름을 조금이나마 쫓아갔다.

 

해당 사진을 보면 피보나치 수열로 처음 DP를 배웠을 때처럼 함수의 호출에서 꽤나 많은 부분의 흐름이 겹친다. 이를 통해 DP로 풀 수 있을 것 같다고 생각했다.

 

DP

처음엔 2차원 DP 배열에서 w, t를 가지고 나중에는 t, h나 w, h로도 풀려고 했으나 역량 부족으로 풀진 못했다. 그래서 다른 블로그들의 해설을 봤다.. 그리고, 나만의 방법으로 다시 한번 푸는 것에 성공했고 그 풀이 과정을 설명하겠다.

 

일단 새로운 예제를 한번 생각해보자.

3 2
2
1
1

 

t = 3, w = 2가 주어지고 t=1일 때 2, t=2일 때 1, t=3일 때 1 위치에서 각각 자두가 떨어진다. 해당 예제를 완전 탐색으로 흐름을 쫓아가면 다음과 같다.

 

 

일단 위의 그림을 통해서도 알 수 있듯이 해당 문제에서 주어진 변수는 총 3가지이다. 자두가 떨어지는 시간, 이동 횟수, 자두의 위치. 여기서 우리가 구해야하는 것은 먹은 자두의 갯수이다. 편의상 자두가 떨어지는 위치는 1,2가 아닌 0,1로 한다.

 

t = 3, w = 2, h = 0일 때는 t=2, w=2, h=0과 t=2, w=1, h=1로 경우의 수를 나눌 수 있고 t = 2, w = 2, h = 0일 때는 t = 1, w = 2, h = 0과 t = 1, w= 1, h = 1인 경우로 나눌 수 있다. 이를 일반화하면 t, w, h에 대해 나눌 수 있는 경우의 수가 (t-1, w, h)와 (t-1, w-1, h^1)임을 알 수 있다.

 

t = 0일 때는 시간이 모두 소진된 것이므로 먹을 수 있는 자두 개수가 0이다. 그럼 가장 아랫단 t = 0일 때 반환되는 자두의 개수는 0이다. 

if (t <= 0) return 0;

 

그리고 t = 1일 때 자두는 1의 위치에서 떨어지므로 t = 1, w = 2, h = 0에서 먹는 자두 개수는 0이다. t = 1, w = 1, h = 1에서 먹는 자두 개수는 1이다. 그럼 이 두 값이 반환되고 t = 2, w = 2, h = 0에서 두 값 중 최댓값을 선택하면 된다. 여기까지 왔으면 대충 이런 코드를 생각할 수 있다. 그리고 t = 2에서 위치에 따라 자두를 먹을 수 있다면 +1 아니면 +0을 하면 된다.

 

if (t <= 0) return 0;

return Math.max(go(t-1, h^1, w-1), go(t-1, h, w)) + (tree[t] == h ? 1 : 0);

 

이 흐름을 따라 계속 타고 올라가다보면 최대한 먹을 수 있는 자두 개수가 나온다. 여기서 이제 DP를 이용해서 겹치는 부분에 대한 문제를 미리 기록해놓았다가 필요 시에 사용하면 된다!! 즉, return 되는 자두의 개수를 DP 배열에 저장하는 것이다.

 

if (t <= 0) return 0;

dp[t][h][w] = Math.max(go(t-1, h^1, w-1), go(t-1, h, w)) + (tree[t] == h ? 1 : 0);
return dp[t][h][w];

 

위의 그림에서는 t=1, w=1, h=1 문제가 겹치는데, 이 때 먹을 수 있는 자두 개수는 1개가 최대임을 이미 구했으므로 t=2, h=1, w=1은 해당 경우의 수를 구하지 않고 바로 DP에 저장된 값을 이용하면 된다.

 

if (t <= 0) return 0;
if (dp[t][h][w]에 값이 있다면) return dp[t][h][w];

dp[t][h][w] = Math.max(go(t-1, h^1, w-1), go(t-1, h, w)) + (tree[t] == h ? 1 : 0);
return dp[t][h][w];

 

이러면 해당 문제의 핵심 로직이 나왔다! 이제 마지막으로 w에 대해서 처리해주기만 하면 된다. w는 0일 때까지는 자두를 먹을 수 있으므로 0보다 작아진 순간부터는 아예 불가능한 경우이다. 즉, 자두 개수에 영향을 줄 수 없다. 그러므로 0을 return하여 자두 개수에 영향을 주지 않도록 한다!

 

if (t <= 0 || w < 0) return 0;
if (dp[t][h][w]에 값이 있다면) return dp[t][h][w];

dp[t][h][w] = Math.max(go(t-1, h^1, w-1), go(t-1, h, w)) + (tree[t] == h ? 1 : 0);
return dp[t][h][w];

 

코드

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

public class Main {
    // 시간제한 2초, 메모리제한 128MB
    static int T, W;
    static int[] tree;
    static int[][][] dp;

    static int go(int t, int h, int w) {

        if (t <= 0 || w < 0) return 0;
        if (dp[t][h][w] != -1) return dp[t][h][w];

        dp[t][h][w] = Math.max(go(t-1, h^1, w-1), go(t-1, h, w)) + (tree[t]-1 == h ? 1 : 0);
        return dp[t][h][w];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        tree = new int[T+1];
        tree[0] = 0;
        for (int i = 1; i <= T; i++) tree[i] = Integer.parseInt(br.readLine());

        dp = new int[T+1][2][W+1];
        // -1로 초기화 하지않으면 dp 값들이 0이 되는데,
        // 0으로 dp 값이 존재하는지 여부를 정해주면 아직 구하지 않은 경우의 수에 대해서 return dp[t][h][w];가 실행된다.
        for (int i = 0; i <= T; i++) {
            for (int j = 0; j < 2; j++) Arrays.fill(dp[i][j], -1);
        }

        System.out.println(Math.max(go(T, 0, W), go(T, 1, W-1)));
    }
}