<백준> 자두나무(Gold 5)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/2240 자두나무 at main · heesoo-park/ForCodeKata

제출 결과

---

정말 정신없이 보낸 3주간의 일정을 마치고 오랜만에 문제를 푸는 시간을 가졌었다.

그랬더니 DP 문제가 난공불락처럼 보이는 신기한 일을 경험...

 

문제 자체는 움직임 제한에 맞춰 가장 많은 자두를 받으면 몇 개인지 맞추면 되는 간단한 문제였지만 이를 어떻게 구현해야할지 갈피를 잘 잡지 못했다.

2차원 DP 배열을 써야할 거 같기도 하고 3차원 DP 배열을 써야할 거 같기도 하고... 그랬다.(둘 다 쓸 수 있더라ㅎㅎ)

3차원 DP 배열을 써야한다고 생각이 든 것은 이전에 미로 문제를 풀 때 열쇠를 먹고 문을 열어야하는 유형에서 3차원으로 해결한 경험이 있기 때문이었다.

 

참고를 해서 문제를 해결했는데 3차원 DP 배열로 잡고 진행했다.

dp[위치][정보][움직임] 으로 결정했다.

위치는 현재 어느 나무에 있는지, 정보는 자두가 어느 나무에서 떨어지는지, 움직임은 자두가 움직일 수 있는 횟수이다.

 

그렇게 해서 바텀업 방식으로 메모이제이션을 했다.

이번에 자두가 떨어지는 나무가 1인지 2인지로 조건을 걸고 그 안에서 dp 배열 값을 업데이트 해줬다.

각각의 조건문 블록에서 dp[1][i][j]와 dp[2][i][j] 값을 업데이트한다.

나무가 1이라면 dp[1][i][j]에는 dp[1][i - 1][j](1에 있으면서 j번 움직일 수 있을 때 이전 정보에 대한 dp 값)에 1을 더한 것과 dp[2][i - 1][j - 1](2에 있으면서 j - 1번 움직일 수 있을 때 이전 정보에 대한 dp 값)에 1을 더한 것 중 큰 값을 넣어주고 dp[2][i][j]에는 dp[1][i - 1][j - 1](1에 있으면서 j - 1번 움직일 수 있을 때 이전 정보에 대한 dp 값)과 dp[2][i - 1][j](2에 있으면서 j번 움직일 수 있을 때 이전 정보에 대한 dp 값) 중 큰 값을 넣어준다.

전자에서는 1을 더한 것을 비교했는데 그 이유는 자두가 1번 나무로 떨어지고 있을 때 1번으로 오는 케이스를 구하는 것이기 때문에 자두를 1개 얻게 되어 1을 더한 것을 비교하는 것이다.

그렇기에 후자는 자두가 1번 나무로 떨어지고 있지만 2번 나무에 있는 케이스를 구하는 것이기 때문에 1을 더하지 않고 비교하는 것이다.

나무가 2일 때는 1일 때와 반대로 진행된다.

그리고 t 일 때의 움직임에 따른 큰 값을 가져와 정답으로 제출한다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());
        int[] event = new int[t + 1];
        int[][][] dp = new int[3][t + 1][w + 2];
        int answer = 0;
        
        for (int i = 1; i <= t; i++) {
            event[i] = Integer.parseInt(br.readLine());
        }
        
        for (int i = 1; i <= t; i++) {
            for (int j = 1; j <= w + 1; j++) {
                if (event[i] == 1) {
                    dp[1][i][j] = Math.max(dp[1][i - 1][j] + 1, dp[2][i - 1][j - 1] + 1);
                    dp[2][i][j] = Math.max(dp[1][i - 1][j - 1], dp[2][i - 1][j]);
                } else {
                    if (i == 1 && j == 1) continue;
                    
                    dp[1][i][j] = Math.max(dp[1][i - 1][j], dp[2][i - 1][j - 1]);
                    dp[2][i][j] = Math.max(dp[1][i - 1][j - 1] + 1, dp[2][i - 1][j] + 1);
                }
            }
        }
        
        for (int i = 1; i <= w + 1; i++) {
            answer = Math.max(dp[1][t][i], dp[2][t][i]);
        }
        
        System.out.println(answer);
    }
}