백준 14585번: 사수빈탕 [자바]

 

 

🧫 문제 분석

 

✔️ 출처

사수빈탕 골드 5

 

📖 문제

 

 

DP문제로 

주어진 사탕 바구니 위치로 이동하며 최대 개수를 구하는 문제

 

한 번 움질일때마다 사탕바구니의 사탕이 -1이 된다.

 

사탕 바구니를 x,y로 오름차순 정렬해서 

DP + DFS 탐색한다. 

 

 

다른 사람풀이를 보니 bottom-up 으로 푸는 방법도 있다.

---

🔅 문제 풀이

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

public class Main {

    static int n, m;
    static int[][] arr;
    static int[][] dp;


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

        arr = new int[n][2];
        dp = new int[n][300 * 2 + 1]; // x, y가 최대 300까지 이므로 최대 600일까지 가능

        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            arr[i][0] = x;
            arr[i][1] = y;
        }

		// 가장 가까운 사탕 방구니 먼저 탐색하기 위해 정렬
        Arrays.sort(arr, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }

            return o1[0] - o2[0];
        });

        System.out.println(dfs(0, 0, 0, 0));

    }


    private static int dfs(int x, int y, int idx, int preDays) {
        if (idx >= n || preDays >= m){
            return 0;
        }

        if (dp[idx][preDays] != -1) {
            return dp[idx][preDays];
        }

        dp[idx][preDays] = 0;
        for (int i = idx; i < n; i++) {
            int[] pos = arr[i];

            if (pos[0] >= x && pos[1] >= y) {
                int day = pos[0] - x + pos[1] - y + preDays; // 현재 이동하려는 사탕바구니로 가는 일수 + 이전 일수 
                int candyCnt = Math.max(m - day, 0); // 사탕 개수보다 지나온 날이 더 크다면 0 
                dp[idx][preDays] = Math.max(dp[idx][preDays], candyCnt + dfs(pos[0], pos[1], i + 1, day));
            }
        }

        return dp[idx][preDays];
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.