[Algo] 백준 14585 사수빈탕 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/14585

메모리 : 14780 KB

시간 : 140 ms

언어 : Java 11

---

코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] dp = new int[301][301];
        boolean[][] map = new boolean[301][301];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            map[x][y] = true;
        }
        for (int i = 1; i <= 300; i++) {
            if (map[i][0]) {
                dp[i][0] = Math.max(0, M - i);
            }
            dp[i][0] += dp[i - 1][0];

            if (map[0][i]) {
                dp[0][i] = Math.max(0, M - i);
            }
            dp[0][i] += dp[0][i - 1];
        }
        for (int i = 1; i <= 300; i++) {
            for (int j = 1; j <= 300; j++) {
                if (map[i][j]) {
                    dp[i][j] += Math.max(M - (i + j), 0);
                }
                dp[i][j] += Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        System.out.println(dp[300][300]);

    }
}

 

풀이

수빈이가 (0,0)에서 index가 커지는 방향으로만 움직이며 사탕을 먹는 문제이다. 한 번 움직이면 다시 왔던 줄로는 되돌아갈 수 없으니 어떤 사탕을 먹는것이 가장 효율적인지 계산해야한다. 300*300배열이므로 완전탐색으로는 시간초과가 날 것이다. DP로 해당 칸에서 먹을 수 있는 최대 사탕개수를 저장하면서 이동하면 된다. (문제에서 위쪽, 오른쪽으로만 움직일 수 있다는 말이 DP의 힌트가 된다.)

사탕은 시간이 지날수록 1개씩 없어지는데 이것은 움직인 거리와 비례하므로 따로 계산하지 않아도 된다. 위쪽, 오른쪽에서 가진 사탕의 수 중 가장 큰것을 이어받으며 진행하면 된다. 주의해야할 점은 사탕의 개수가 음수가 될 수는 없으므로, 그 처리를 해주어야 했다.