[백준/node.js] 14501번 퇴사

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

14501번: 퇴사

 

문제 분석

분류

다이나믹 프로그래밍, DP

문제 설명

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 각각의 상담은 상담을 완료하는 데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성해 보자.​

입력

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

출력

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

 

소스코드

const [n, ...arr] = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const N = Number(n);
const counsel = arr.map(tp => tp.split(' ').map(Number));

function solution(n, counsel){
    const DP = new Array(N).fill(0);
    
    for (let i = 0; i < n; i++) {
        const [period, profit] = counsel[i];
        if (i + period > N) continue;
        DP[i] = DP[i] + profit;
         
        for (let j = i + period; j < N; j++) {
            DP[j] = Math.max(DP[j], DP[i]);
        }
    }
    return Math.max(...DP);
}

console.log(solution(N, counsel));

 

문제풀이

const [n, ...arr] = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const N = Number(n);
const counsel = arr.map(tp => tp.split(' ').map(Number));

퇴사까지의 기간을 나타내는 N을 입력받고, 서로 다른 사람의 상담 예약을 counsel에 입력받는다.
node.js로 입력받을 때, String으로 저장되기 때문에 계산을 위해서 Number로 바꾸어준다.
상담예약은 map을 사용해서 걸리는 기간인 T와 받을 수 있는 금액인 P을 나눠서 저장해 준다.

function solution(n, counsel){
    const DP = new Array(N).fill(0);
    
    for (let i = 0; i < n; i++) {
        const [period, profit] = counsel[i];
        if (i + period > N) continue;
        DP[i] = DP[i] + profit;
         
        for (let j = i + period; j < N; j++) {
            DP[j] = Math.max(DP[j], DP[i]);
        }
    }
    return Math.max(...DP);
}

모든 상황을 고려해서 최대 수익을 찾아야 하기 때문에 Greedy가 아닌 DP로 문제를 풀었다.

현재까지의 수익을 저장할 수 있는 DP를 0으로 초기화해 둔다.
퇴사 전까지를 범위로 잡고, 상담기간과 수익을 각각 period, profit에 저장하여 사용했다.

1. 퇴사 전에 처리할 수 없는 일은 continue로 건너뛴다.
2. 이미 진행한 상담으로 생긴 수익 + 해당일에 있는 상담을 진행했을 때 얻는 수익을 DP에 저장한다.
3. 해당 상담을 진행했을 경우와 다른 상담을 진행했을 경우의 최댓값을 비교하여 DP에 저장한다.

N = 7인 경우에 상담 일정표 예시이다.

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200

1-4일 상담은 총 3일이 걸리기 때문에, 2, 3일에는 상담을 할 수 없어서  DP는 [10, 0, 0, 10, 10, 10, 10]이 된다. 
2-7일 상담은 1일에 진행한 상담보다 수익이 크기 때문에 DP는 [10, 20, 0, 10, 10, 10, 20]이 된다. 
3-4일 상담은 1-4일에 진행한 수익과 같기 때문에 DP는 [10, 20, 10, 10, 10, 10, 20]이 된다. 
4-5일 상담은 (이미 진행한 상담+이번 상담)으로 수익이 30이라 DP는 [10, 20, 10, 30, 30, 30, 30]이 된다. 

마찬가지로 계속 진행하다 보면, 최대 이익은 10+20+15=45으로 나오게 된다.

DP	0	1	2	3	4	5	6
i = 0	0	0	0	0	0	0	0
i = 1	10	0	0	10	10	10	10
i = 2	10	20	0	10	10	10	20
i = 3	10	20	10	10	10	10	20
i = 4	10	20	10	30	30	30	30
i = 5	10	20	10	30	45	30	45
i = 6	10	20	10	30	45	30	45

 

console.log(solution(N, counsel));

완성된 solution함수에 N과  counsel을 넘겨주고, 출력하면 끝나게 된다.