서울에서 경산까지

한 며칠 고민하다가 답을 못 구할 것 같아서 문제 제목으로 검색했더니 KOI 초등부 문제였다. 초등부 문제도 못풀었다는 생각을 하니까 참 자괴감도 들고 내가 잘 하고 있는건지 자신감도 좀 떨어지는 것 같다. 이정도 수준의 동적계획법 문제는 초등학생들도 푸는구나...

 

문제는 이곳에서 볼 수 있다.

 

결국 동적계획법은 격자를 만들고 그 격자를 정의 해야 한다. 결국 이 점화식을 생각해 낼 수 있느냐 없느냐가 문제를 풀 수 있느냐 없느냐를 나누게 된다.

 

기본적으로 동적계획법 문제가 나오면 (일단 처음에는 그게 동적 계획법으로 푸는 문제인지 모르니까) 완전탐색 방법으로 문제를 생각해 본 후 -> 이미 계산했던 답을 재활용 할 수 있는지 생각해 본다. 재활용이 가능하다면 동적계획법을 활용할 수 있다.

 

이 문제에서도 2차원 배열을 정의한 후 각자를 [i] 번째 도시에 [j] 분 이전에 도착할 수 있다면 그때 까지의 최대 모금액 으로 정의 한다. 사실 이런 생각을 했으면 문제를 푼 것이나 다름없다. 한 가지 고려해야 할 것은 시간적으로 도착할 수 없는 곳을 처리해 줘야한다는 것이다.(그렇지 않으면 도착하지 않은 도시에서 출발하는 경우가 발생한다)

    public int solution(int K, int[][] travel) {
        int[][] cache = new int[travel.length+1][K+1];
        for (int i = 1; i < travel.length+1; i++) {
            for (int j = 0; j < K+1; j++) {
                int maxMoney = -1;
                int walkingTime = travel[i-1][0];
                int walkingMoney = travel[i-1][1];
                int ridingTime = travel[i-1][2];
                int ridingMoney = travel[i-1][3];
                if (j >= walkingTime && walkingMoney + cache[i-1][j-walkingTime] > maxMoney) {
                    maxMoney = walkingMoney + cache[i-1][j-walkingTime];
                }
                if (j >= ridingTime && ridingMoney + cache[i-1][j-ridingTime] > maxMoney) {
                    maxMoney = ridingMoney + cache[i-1][j-ridingTime];
                }
                cache[i][j] = maxMoney == -1 ? Integer.MAX_VALUE : maxMoney;
            }
        }
        return cache[travel.length][K];
    }