14863번 - 서울에서 경산까지

2024-11-26

#JAVA#백준

문제 링크

문제 풀이 시간 : 30분

문제 풀이 :

문제를 읽자마자 dp로 풀어야겠구나 라는 생각은 했는데,

어떻게 풀어야하나 고민을 했다.

근데 N과 K가 각각 최대 100과 100,000 이었기 때문에 2차원 배열로 해서 전체 탐색을 해도 시간 안에 충분히 할 수 있겠다 라는 생각이 들었다.

그래서 2차원 배열을 만들고

가로를 시간, 세로를 도시 번호로 해서

각 도시마다 갈 수 있는 모든 경우를 계산했다.

배낭 문제와 비슷한 방식이다.

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public 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 k = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n][4];
        int[][] dp = new int[n][k + 1];

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

        dp[0][arr[0][0]] = arr[0][1];
        dp[0][arr[0][2]] = arr[0][3];

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                if (dp[i - 1][j] != 0) {

                    if(j + arr[i][0] <= k)
                        dp[i][j + arr[i][0]] = Math.max(dp[i - 1][j] + arr[i][1], dp[i][j + arr[i][0]]);
                    if(j + arr[i][2]<=k)
                        dp[i][j + arr[i][2]] = Math.max(dp[i - 1][j] + arr[i][3], dp[i][j + arr[i][2]]);
                }
            }
        }

        int ans = 0;
        for (int i = 0; i <= k; i++) {
            ans = Math.max(dp[n - 1][i], ans);

        }
        System.out.println(ans);
    }
}

무조건 정답이라는 생각으로 제출을 했는데 29점을 받았다.

그래서 문제 조건을 봤더니

1번만 만족하면 29점인 것이다.

근데 아무리 생각해도 시간초과가 날 수가 없는데,,,

라는 생각으로 질문 게시판을 조금 뒤져봤더니

Java

2 4
2 5 2 2
2 2 2 2

이런 반례가 있었다.

해당 테스트 케이스의 정답은 7이다.

근데 내 코드에서는 첫번째 도시의 경우를 dp 배열에 옮기는 과정에서 두 경우의 시간이 같은 경우를 고려하지 않았다.

Java

dp[0][arr[0][0]] = arr[0][1];
dp[0][arr[0][2]] = arr[0][3];

그래서 뒤에 나온 2가 더 큰 5를 덮어 씌운 것이다.

그래서 해당 부분을 아래와 같이 수정해주니 통과를 하였다.

Java

dp[0][arr[0][0]] = arr[0][1];
dp[0][arr[0][2]] = Math.max(arr[0][3], dp[0][arr[0][2]]);

전체 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public 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 k = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n][4];
        int[][] dp = new int[n][k + 1];

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

        dp[0][arr[0][0]] = arr[0][1];
        dp[0][arr[0][2]] = Math.max(arr[0][3], dp[0][arr[0][2]]);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                if (dp[i - 1][j] != 0) {
                    if(j + arr[i][0] <= k)
                        dp[i][j + arr[i][0]] = Math.max(dp[i - 1][j] + arr[i][1], dp[i][j + arr[i][0]]);
                    if(j + arr[i][2]<=k)
                        dp[i][j + arr[i][2]] = Math.max(dp[i - 1][j] + arr[i][3], dp[i][j + arr[i][2]]);
                }
            }
        }

        int ans = 0;
        for (int i = 0; i <= k; i++) {
            ans = Math.max(dp[n - 1][i], ans);

        }
        System.out.println(ans);
    }
}