[백준] 14501번 : 퇴사

14501번: 퇴사

# 문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

 

3	5	1	1	2	4	2
10	20	10	20	15	40	200

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

# 입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

# 출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

 

# 예제 입력 1

7

3 10

5 20

1 10

1 20

2 15

4 40

2 200

# 예제 출력 1

45

---

이 문제에 대해선 다양한 방법으로 접근이 가능 할 것 같다.

DFS를 이용해도 되고, Recursive한 방법 그리고 동적 프로그래밍을 이용해도 될 것 같다.

 

이번엔 재귀적 + 동적 프로그래밍으로 풀어보았다. 입력 값이 크지 않고 제한 시간과 메모리가 빡빡하지 않은 문제라 DP가 없어도 무관하다.

 

문제의 핵심은 주어진 N 일 중에 최대한 많은 날짜를 일하자는 것이 아닌, 최대한 많은 돈을 벌자 라고 생각한다. 사실 그게 그거아닌가 싶지만 내 생각은 그렇다. 그러므로 중간에 일을 안하고, 그 다음날 일하는 것이 더 이득인 경우도 있다는 것.

 

7     //7일

3 10 //{term[1], pay[1]}

5 20 //{term[2], pay[2]} 

1 10 //{term[3], pay[3]}

1 20 //{term[4], pay[4]}

2 15 //{term[5], pay[5]}

4 40 //{term[6], pay[6]}

2 200 //{term[7], pay[7]}

 

주인공 백준이는 첫 날 다음과 같은 선택을 할 수 있다.

1) 1일에 잡힌 상담을 이행하고 스케쥴이 끝난 다음 날로 간다. 

2) 다음 날 일정을 이행한다.

 

만약 첫 날에 잡힌 일정을 이행했다고 가정하면, 그 고객을 배웅하고 다음 날부터 일할 수 있으므로 1일 + 3일 = 4일 부터 일을 할 수 있다. 여기서 다시 결정을 해야한다.

 

1) 4일에 잡힌 스케쥴 이행

2) 4일은 쉬고 5일 째에 일하기

 

놀랍게도 4일에 예약한 고객은 하루만에 시마이 칠 수 있다. 정말 고마운 고객이 아닐 수 없다. 그러므로 4일에 일을 안하는 것은 좋지 못한 선택이다.

 

이렇게 분기점에서 더 큰 돈을 벌 수 있는 곳으로 재귀 호출을 하며 진행하면 쉽게 풀 수 있다.

 

당일 일하고-> 종료된 다음날로 가기 OR 다음 날로 가기

dp[i] = max( get(day + term[day]) + pay[day], get(day + 1) );

 

이 코드만 활용하면 된다.

 

# Whole Code </>

public class Main {

    static int[] term;
    static int[] pay;
    static int[] dp;
    static int n;

    static int get(int day){

        if(day > n) return 0;
        if(dp[day] != 0) return dp[day];
        if(day + term[day] > n + 1) return DFS(day+1);

        dp[day] = Math.max(get(day + term[day]) + pay[day], get(day+1));

        return dp[day];
    }

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

        term = new int[n+1];
        pay = new int[n+1];
        dp = new int[n+1];

        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            term[i] = Integer.parseInt(st.nextToken());
            pay[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(get(1));
        Arrays.stream(dp).forEach(i->System.out.print(i + " "));
    }
}