15486 - 퇴사2(dp)

문제:

15486번: 퇴사 2 (acmicpc.net)

 

풀이:

전형적인 dp를 이용하는 문제라고 볼 수 있다.

dp는 Dynamic Programming의 약자로 동적 계획법이라는 뜻이다.

즉, 하나의 큰 문제를 여러개의 작은 문제로 나누어 푼다는 뜻이다.

위의 문제를 풀기 위한 가장 좋은 방법은, 각 일수별로 얼마를 버는게 최대 이익일지 체크하며,
마지막날 까지 진행하는 것이다.

예를들어 7일차에 벌 수 있는 최대 금액을 구하려면, 6일차를 알아야하며, 6일차를 알려면 5일차를 알아야한다.
이렇게 1일차까지 거슬러가므로, 각 일수에 따라 최대 금액을 구하며 마지막날의 최대 금액을 구해야 한다.

 

각 일수별로 최대 금액을 산정하려면 어떤 일수에서, 어떤 경우의수를 고려해야하는지 미리 저장해두면 좋을 것이다.

예를들어 2일차에 5일이걸리고 20원을 벌 수 있다 했을때, 이는 6일차에서 고려해주면 된다.
'1일차에서 벌 수 있는돈 + 2~6일차에서 벌 수 있는돈' vs '그동안 1~6일차 까지 벌수 있는 최대 액수'

이 둘을 비교해서 둘중의 큰 값이 6일차에서 벌 수 있는 최대 액수이다.

 

이를 쉽게 하기 위해 아래와 같이 입력을 받아줬다.

static int N;
static List<Queue<int[]>> schedule;
static int[] max;

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

    max = new int[N+1];
    schedule = new ArrayList<>();
    for (int i = 0; i < N+1; i++) {
        schedule.add(new LinkedList<>());
    }

    for (int i = 1; i < N+1; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int term = Integer.parseInt(st.nextToken());  // 기간
        int reward = Integer.parseInt(st.nextToken());  // 보상
        if (i + term <= N+1) { // 출발지점과 보상을 저장
            schedule.get(i + term - 1).add(new int[]{i, reward});
        }
    }

    findMax();

    System.out.println(max[N]);

}

6에서 2일차를 고려해야 한다면, List의 6번째 칸에 2일차, 15원 고려해야 한다는 것을 저장해둔다.

그렇다면 나중에 '1일차에서 벌 수 있는돈 + 2~6일차에서 벌 수 있는돈' vs '그동안 1~6일차 까지 벌수 있는 최대 액수'
를 비교하기 편할 것이다.

 

findMax() 메서드는 아래와 같이 작성해주었다.

static void findMax() {
    for (int i = 1; i <= N; i++) {
        max[i] = max[i-1];
        while (!schedule.get(i).isEmpty()) {
            int[] arr = schedule.get(i).poll();
            max[i] = Math.max(max[i], arr[1] + max[arr[0]-1]);
        }
    }
}

1. 이전 날짜의 최대 금액을 오늘 날짜의 최대 금액으로 설정해놓는다. 
   만일 오늘 어떤 작업도 선택할 수 없다면, 이전 날짜에서 벌 수 있는 최대 금액이 오늘의 최대 금액과 같아지기 때문.
2.  입력받을때 오늘 고려해야할 날과 액수를 저장해놓았다. 그 날과 액수는 큐에 담겨있다.
   그렇다면 아래와 같은 작업이 가능해진다.
    '1일차에서 벌 수 있는돈 + 2~6일차에서 벌 수 있는돈' vs '그동안 1~6일차 까지 벌수 있는 최대 액수'
3. 여러 날과 액수를 고려해야 할 수 있고, 각각 모두 큐에 저장되어 있으니 2번 과정은 큐가 빌동안 반복한다.
4. 1~3번 과정을 1일차부터 마지막 날까지 반복한다.

 

전체 코드:

package part5;

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

public class 퇴사2_15486번 {
    static int N;
    static List<Queue<int[]>> schedule;
    static int[] max;

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

        max = new int[N+1];
        schedule = new ArrayList<>();
        for (int i = 0; i < N+1; i++) {
            schedule.add(new LinkedList<>());
        }

        for (int i = 1; i < N+1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int term = Integer.parseInt(st.nextToken());  // 기간
            int reward = Integer.parseInt(st.nextToken());  // 보상
            if (i + term <= N+1) { // 출발지점과 보상을 저장
                schedule.get(i + term - 1).add(new int[]{i, reward});
            }
        }

        findMax();

        System.out.println(max[N]);

    }
    static void findMax() {
        for (int i = 1; i <= N; i++) {
            max[i] = max[i-1];
            while (!schedule.get(i).isEmpty()) {
                int[] arr = schedule.get(i).poll();
                max[i] = Math.max(max[i], arr[1] + max[arr[0]-1]);
            }
        }
    }
}

 

모든 과정이 끝났으면 max[N]에서는 기간내 벌 수 있는 최대 금액이 저장되어 있을 것이다.

 

시행착오:

dp를 떠올리지 못하고, 재귀를 이용해 버렸다.
덕분에 불필요한 과정을 많이 겪게되었고, 시간이 초과되었다.

dfs와 bfs만큼 연습이 필요할 듯 하다.

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

public class 퇴사2_15486번_시간초과 {
    static int N;
    static int[][] schedule;
    static int max;

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

        schedule = new int[N+1][2];
        for (int i = 1; i < N+1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            schedule[i][0] = Integer.parseInt(st.nextToken());  // 기간
            schedule[i][1] = Integer.parseInt(st.nextToken());  // 보상
        }

        findMax(1, 0);

        System.out.println(max);
    }
    static void findMax(int start, int sum) {
        for (int i = start; i < N+1; i++) {
            if (schedule[i][0] == 1) {
                sum += schedule[i][1];
            } else if (schedule[i][0] + i <= N+1) {
                findMax(schedule[i][0] + i, sum + schedule[i][1]);
            }
        }
        max = Math.max(max, sum);
    }
}