[Algorithm] 백준 14501 퇴사 - node.js

이 글은 백준 14501번 퇴사를 풀이한다. 알고리즘은 javascript를 이용해 구현하였다.

문제

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

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

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

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

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

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

예제 입력 2

10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

출력

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

예제 출력 1

45

예제 출력 2

55

풀이

접근

백준이가 퇴사일까지 할 수 있는 상담 조합은 다음 둘 중 하나에 속한다.

• 첫 날에 상담한 경우
• 첫 날에 상담하지 않은 경우

그렇다면 백준이가 퇴사일까지 일했을 때 얻을 수 있는 최대 수익은 다음과 같다.

• 첫 날에 상담한 경우: (첫 상담 금액) + (첫 상담 기간 후부터 퇴사일까지 일했을 때 얻을 수 있는 최대 수익)
• 첫 날에 상담하지 않은 경우: (둘째 날부터 퇴사일까지 일했을 때 얻을 수 있는 최대 수익)

최대 수익을 구하기 위해 함수를 재귀 호출하는데, 이때 각 부분 문제들이 같은 부분 문제에 의존하는 경우가 많기 때문에 동적 계획법을 이용해 코드를 구현했다.

//maxPay(n): n+1일(n=0, 1, ...)부터 N일까지 일했을 때 얻을 수 있는 최대 수익
maxPay(n) = Max(getMaxPay(n+1), (n+t-1)<dDay? p+getMaxPay(n+t): getMaxPay(n+t))

알고리즘

다음은 상담 시작일 n을 인자로 받아 퇴사일(N일)까지 일했을 때 얻을 수 있는 최대 수익을 반환하는 getMaxPay()의 수도 코드이다. 시작일을 인자로 받는 이유는 앞의 상담 날짜에 따라 후에 할 수 있는 상담이 정해지기 때문(해당 상담 기간 후에 다른 상담을 진행할 수 있기 때문)이다.

• n일부터 퇴사일(N일)까지 일했을 때 얻을 수 있는 최대 수익을 최초에는 계산하고 캐시에 저장한다. 같은 n에 대해 함수가 다시 호출되면 캐시에서 해당 값을 리턴한다.
• getMaxPay(n)는 다음 두 값 중 큰 값을 반환한다.
  • n일에 일하지 않는 경우: maxPay(n+1)
  • n일에 일하는 경우: (n+t-1)<dDay ? p+maxPay(n+t): maxPay(n+t) - n일에 상담을 진행하면 다음 상담은 (n+t)일에 진행할 수 있다. n일의 상담 기간이 근무 기간 안에 포함되어야 진행할 수 있으므로 상담이 가능할 때에만 상담 금액을 더해준다.
• n일이 퇴사일 이후이면 상담을 진행할 수 없으므로 0을 리턴한다.

const getMaxPay = (n) => {
    if(n>dDay){
        return 0;
    }
    if(memo[n]!==undefined){
        return memo[n];
    }

    const [t, p] = schedule[n];
    memo[n] = Math.max(getMaxPay(n+1), n+t-1<dDay? p+getMaxPay(n+t): getMaxPay(n+t));
    return memo[n];
};

구현

코드

const input = [];
//dDay: 퇴사일
//schedule: 상담 일정. [상담 기간, 금액]을 담는 배열
//memo: n일부터 퇴사일까지 일했을 때 얻을 수 있는 최대 수익을 담는 배열
let dDay, schedule, memo;

const strToNumArr = (str) => str.split(" ").map((numString) => Number(numString));

require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", function (line) {
    input.push(line.trim());
  })
  .on("close", function () {
    dDay = Number(input.shift());
    schedule = input.map((str)=>strToNumArr(str));
    memo = [...Array(dDay)];

    //n=0(1일), 1(2일), ...
    console.log(getMaxPay(0));
  });

const getMaxPay = (n) => {
    //기저사례: 상담일이 퇴사일 이후일 때
    if(n>=dDay){
        return 0;
    }
    //이미 계산되었을 때
    if(memo[n]!==undefined){
        return memo[n];
    }


    const [t, p] = schedule[n];
    memo[n] = Math.max(getMaxPay(n+1), n+t-1<dDay? p+getMaxPay(n+t): getMaxPay(n+t));
    return memo[n];
};

시간 복잡도

동적 계획법은 한 번 계산한 값은 다시 계산하지 않고 캐시를 참조하기 때문에 시간복잡도는 다음과 같다. 따라서 위 알고리즘의 시간 복잡도는 O(n)이다.

(존재하는 부분 문제의 수) X (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)