백준 14863 (서울에서 경산까지) - java

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

 

문제

 

배우 한정올 씨는 이번 여름에 서울에서 경산까지 자선 여행을 하면서 모금 활동을 진행할 계획이다. 자선 여행에서 거쳐 가게 될 도시의 개수와 순서는 미리 정해져 있으며, 자선 여행은 서울에서 시작하여 각 도시를 정해진 순서대로 단 한 번씩 방문한 후 경산에서 끝난다. 서울을 제외한 도시의 개수를 N 이라 하자. 이때 서울에서 두 번째 도시까지 가는 구간을 구간 1, 두 번째 도시부터 세 번째 도시까지 가는 구간을 구간 2와 같이 부르기로 하며, 마지막 목적지인 경산에 도착하는 구간을 구간 N 이라 하자. 즉, 구간의 전체 개수는 N이다. 구간 사이의 이동은 도보 혹은 자전거 어느 한 쪽을 이용하게 되는데, 각 구간에는 도보로 이동할 때 걸리는 시간(분), 이때 얻게 되는 모금액(원), 자전거로 이동할 때 걸리는 시간(분), 이때 얻게 되는 모금액(원)이 정해져 있다.

예를 들어, 서울과 경산 사이에 2개의 도시가 있는 다음과 같은 경우(N = 3)를 생각해 보자.

인접한 도시 사이를 도보로 이동하는지 자전거로 이동하는지에 따라 전체 모금액이나 걸리는 시간에 차이가 생기게 된다. 한정올 씨는 전체 모금액을 가능한 많이 얻는 방법을 찾고 싶어 한다. 위의 예에서는 시간이 충분하다면 모든 구간을 도보로 이동하는 것이 모금액을 최대로 하는 방법이며, 모금액은 200+370+250 = 820원, 여행에 걸리는 시간은 500+800+700 = 2,000분이다.

그러나 한정올 씨는 바쁜 스케줄로 인해 자선 여행을 위해 보낼 수 있는 시간이 K분(K는 자연수)으로 한정되어 있다. 위의 예에서 만약 K = 1,650이라면, 1, 2번 구간은 도보로 이동하고 3번 구간은 자전거로 이동하여 모금액을 660원으로 하는 것이 가장 좋은 방법이며, 이때 걸리는 시간은 1,600분이다.

위와 같이 각 구간별로 도보 및 자전거로 이동하는 경우 걸리는 시간과 모금액이 주어질 때, 제한시간 이내로 서울에서 경산까지 여행하면서 모금할 수 있는 최대 금액을 찾는 프로그램을 작성하시오. (제한시간 이내에 여행하는 방법은 항상 존재한다.)

 

유형 : DP

 

접근 방식

• 모든 지점을 지나쳐야 하기 때문에 배열의 값을 0으로 초기화하고 전에 지점 (i-1, j) 지점에 값이 있는 것을 계속 갱신한다.
• n개의 모든 지점을 지나쳤을 때 (n,0 ~ k)까지의 값 중 가장 큰 것을 찾는다.

 

코드

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

public class BOJ_14863_서울에서_경산까지 {

    static int n,k;
    static int[][] board;
    static int MIN = Integer.MIN_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        board = new int[n+1][4];

        for(int i = 1 ; i <= n ; i++) {
            st = new StringTokenizer(br.readLine()," ");

            int tw = Integer.parseInt(st.nextToken());
            int cw = Integer.parseInt(st.nextToken());
            int tb = Integer.parseInt(st.nextToken());
            int cb = Integer.parseInt(st.nextToken());

            board[i][0] = tw;
            board[i][1] = cw;
            board[i][2] = tb;
            board[i][3] = cb;
        }

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

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

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

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

        int result = 0;

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

        System.out.println(result);
        br.close();
    }

}