백준 14501 : 퇴사

💡기본 정보

유형
: 시뮬레이션
풀이 날짜
: 2025년 01월16일 
풀이방법 한줄 요약
: 가능한 모든 경우의 수를 계산하면서 가장 최대로 이익을 낼 수 있는 경우를 출력함 

 

💡문제에서 구해야 할 것

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

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

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

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

-> 이 경우 1일보다 클 수 있기 때문에 모든 상담을 할 수 없음 
     : 1일에 상담을 하게 되면 2,3일은 상담이 불가능함 2일에 있는 상담을 하게 되면 3,4,5,6일에 잡혀있는 상담은 할 수 없음 

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

상담을 적절히 했을 때 얻을 수 있는 최대 수익

- 입력 : 첫째 줄에 N이 주어짐
            둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어짐. 1일부터 N일까지 순서대로 주어짐 
            (1<= Ti <= 5 , 1<=Pi<=1000)
  출력 : 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력

 

💡알고리즘 설계

- answer을 money가 최대 이익이 되도록 설정

- 순환하면서 다음날을 계속해서 체크함 

 

💡CODE

const fs = require("fs");
const input = fs.readFileSync(0,"utf8").toString().trim().split("\n");
const N = parseInt(input[0]);
const table = [];
let answer = 0;

function talk(){
    for(let i =1;i<=N;i++){
        table.push(input[i].split(" ").map(Number));
    }
    check(0,0);
    return answer;
}

function check(day,money){
    answer = Math.max(answer,money);
    for(let i = day; i<N;i++){
        let [D,M]=table[i];
        let nextDay = i+ D;
        check(nextDay,nextDay<N+1?money + M : money);
    }
}
console.log(talk());

 

💡시간복잡도

 

💡 틀린 이유 & 틀린 부분 수정

재귀적으로 check함수를 불러와서 nextDay에 대한 점검을 확실하게 하지 않았음 

 

💡 다른 풀이 or 기억할정보

check(0,0) : 갱신해서 풀이해야 하므로 0,0으로 정의 day와 money를 0으로 설정하는 것