[Java] 2240번: 자두나무 Gold 5

문제 링크

1차 시도

문제를 고민하다가 문득 떠오른 방법은,
이어지는 값들의 최대 길이들을 우선순위 큐에 넣어서 긴 순서대로 꺼내서 쓰면 되지 않을까? 였다.

근데 2%에서 틀렸다.

문제를 다시 읽어보니 시작할 때 위치는 1인데,
최대 길이가 처음에 주어진다면 움직이지 않아도 되기 때문에
한 번 더 움직일 수 있는데 그 부분을 고려해주지 않았다..

그냥 다른 방식을 생각해보기로 했다~..

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));

        // T, W 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        // 자두 입력 받기
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int before = 0, count = 1;
        for (int i = 0; i < T; i++) {
            int now = Integer.parseInt(br.readLine());
            if (before == now) {
                count++;
            } else {
                pq.offer(count);
                count = 1;
            }
            before = now;
        }
        pq.offer(count); // 마지막 값 처리

        // 정답 구하기
        int ans = 0;
        W++;
        while (W-- > 0) {
            ans += pq.poll();
        }

        System.out.println(ans);
    }
}

정답

아이디어는 이렇다!

dp 문제를 풀 때는 언제나
1. dp 배열의 의미를 정의하고
2. dp[i]가 어떻게 만들어 지는지
에 대해서 생각하면 된다!!

나는 dp[i]를 2차원 배열로 생각해서, dp[t][w]처럼 2차원 배열로 설계했다.
왜냐면 언제 이동할지가 최적의 값을 결정하기 때문에, 이동했냐 안 했냐를 고려해야하기 때문이다.

풀다보니 예전에 bfs문제집 중에서, 골드 3 이상의 난이도로 올라가면 3차원 이상으로 푸는 문제가 생각났다. 벽 부수고 이동하기였나?
그 문제도 언제 벽을 부수는 것이 최적의 값인지 모르기 때문에 벽을 부순 차원과 벽을 부수지 않은 차원을 동시에 고려해야했다.

먼저 T와 W를 입력 받아서 T는 편의를 위해서 T+1, W는 0 ~ W번 만큼 위치이동이 가능하니 (T+1)*(W+1) 크기의 배열을 만들었다.

그래서 DP[t][w]의 의미는 t초 시간에 w만큼 위치를 이동했을 때의 획득할 수 있는 자두의 최댓값이다.

내가 말한대로 dp배열의 의미를 정의했으니, 이제 dp[t][w]가 어떻게 만들어지는 지를 생각해보면 된다.

언제 이동하는 것이 최댓값인지를 결정해야 한다.
그렇기에 모든 위치에서 이동하는 것을 고려해보는 것이다!!
즉, 현재 위치로 오면서 이동을 한다고 늘 생각하고 결정하면 된다.

예를 들어 문제의 입력 예시를 생각해보자.

7 2
2
1
1
2
2
1
1

여기서 초반의 부분을 생각하면서 이해해보자.

시작 위치는 1이고, 현재 시간은 t = 1이고, 자두는 2에 떨어진다.

1. dp[1][0] = 0: 시작 위치는 1이고, 자두는 2에 떨어지기 때문에 0이다.
2. dp[1][1] = 1: 한 번 이동을 했다면 현재 위치는 2이고, 자두는 2에 떨어지기 때문에 1이다.
3. dp[1][2] = 0: 두 번 이동을 했다면 현재 위치는 1이기 때문에 0이다.

이제 부터가 중요하다.
현재 시간은 t = 2이고, 자두는 1에 떨어진다.

여기서 고려할 케이스는 두 가지다.

1. t = 2의 자두가 떨어지기 직전에 이동하는 경우이고,
2. 이전에 이미 이동을 끝낸 경우이다.

실제로 적용해보자!

1. dp[2][0] = 1: 이동을 하지 않았기에 현재 위치는 시작 위치인 1이고, 자두는 1에 떨어지기 때문에 dp[1][0] + 1 이다.

2. dp[2][1] = 1:

   • 이동을 하기 전의 값은 dp[1][0]이고, 이동후의 위치는 2이므로 자두를 받을 수 없다.
   • 이전에 이미 이동을 끝냈을 경우의 값인 dp[1][1]과 이동후의 위치는 2이므로 자두를 받을 수 없다.
     따라서 0 + 0 과 1 + 0 중 더 큰 값인 1이다.

3. dp[2][2] = 2:

   • 이동을 하기 전의 값은 dp[1][1]이고, 이동후의 위치는 1이므로 자두를 받을 수 있다.
   • 이전에 이미 이동을 끝냈을 경우의 값인 dp[1][2]과 이동후의 위치는 1이므로 자두를 받을 수 있다.
     따라서 dp[1][1] + 1 과 dp[1][2] + 1 중 더 큰 값인 2가 저장된다.

이런 식으로 dp[t][w]가 결정된다!!

이제 이것을 식으로 옮기면 된다!

나무는 1과 2밖에 존재하지 않으므로 이동 횟수의 짝수와 홀수 유무로 위치를 결정지을 수 있다.
그래서 현재 위치를 고려하여 현재 위치에 떨어지는 자두의 값으로 미리 배열을 초기화해주면 된다.

이 경우가 아까 말한 고려할 케이스 두 가지중에서 2번에 해당한다. 이미 이동을 끝마친 상태이기에 현재 위치에 떨어지는 자두의 값을 고려해서 값을 초기화하는 것이다.

그런 다음에 바로 직전에 이동을 했을 때의 값과 비교하는 로직을 아래에 마저 작성해주면 된다.

당연히 이동을 한 번 한 경우에만 고려할 수 있으므로 if문을 통해서 조건을 걸어서 둘 중 최댓값으로 갱신해가면 DP배열을 모두 완성할 수 있다!

조금 어렵긴 했다~..🤮

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));

        // T, W 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        // 자두 입력 받기
        int[] plum = new int[T + 1];
        for (int i = 1; i <= T; i++) {
            plum[i] = Integer.parseInt(br.readLine());
        }

        // DP
        int[][] dp = new int[T + 1][W + 1];
        for (int t = 1; t <= T; t++) {

            for (int w = 0; w <= W; w++) {
                // 시작 위치: 1 / 홀수번 이동 후 위치: 2 / 짝수번 이동 후 위치: 1
                int position = (w % 2 == 0) ? 1 : 2;

                if (plum[t] == position) { // 자두가 현재 위치에 떨어지면
                    dp[t][w] = dp[t - 1][w] + 1; // 이전 시간의 값에서 1 증가
                } else {
                    dp[t][w] = dp[t - 1][w]; // 이전 시간의 값을 유지
                }

                if (w > 0) { // 1번 이상 이동한 경우라면,
                    // 이미 이동한 적 있는 결과의 최댓값 vs 이동하기 직전 시간의 최댓값 + 1(지금 이동하면서 발생하는 자두) 
                    dp[t][w] = Math.max(dp[t][w], dp[t - 1][w - 1] + (plum[t] == position ? 1 : 0));
                }
            }
        }

        // 출력
        int ans = 0;
        for (int w = 0; w <= W; w++) {
            ans = Math.max(ans, dp[T][w]);
        }
        System.out.println(ans);
    }
}