15486 : 퇴사2

💡기본 정보

유형
: DP
풀이 날짜
: 2025년 01월 31일 
풀이방법 한줄 요약
: i번째 날의 일을 선택하는지 안하는지에 맞춰 최댓값 확인

 

💡문제에서 구해야 할 것

상담원으로 일하고 잇는 백준이는 퇴사를 하고자 함
오늘부터 N+1일 째 되는 날 퇴사를 하기 위해서 남은 N일 동안 최대한 많은 상담을 하려고함 
백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁했고 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아둠 
Ti : 상담을 완료하는데 걸리는 기간
Pi : 상담을 했을 때 받을 수있는 금액 

N=7인 경우에 다음과 같음
1일에 잡혀있는 상담은 총 3일이 걸리며 상담했을 때 받을 수 있는 금액은 10 , 5일에 잡혀있는 상담은 총 2일이 걸리며 받을 수 있는 금액은 15
상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에 모든 상담을 할 수는 없음
상담을 적절히 했을 때, 백준이가 얻는 최대 수익을 구하는 프로그램
- 입력 : 첫째 줄에 N이 주어짐
            둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며 1일부터 N일까지 순서대로 주어짐
- 출력 : 첫째 줄에 백준이가 얻을 수 있는 최대 이익 

💡알고리즘 설계

-dp[i]를 퇴직일까지 얻을 수 있는 최대 수익이라고 할 때
- i번째 일 선택 : dp[i]=P[i] + dp[i+T[i]]
  i번째 일 선택 안하면 : dp[i] = dp[i+1]

 

💡CODE

const fs = require("fs");
const input = fs.readFileSync(0,"utf8").toString().trim().split("\n");
const N = parseInt(input[0]);
const T = [];
const P = [];
const dp = new Array(N + 1).fill(0);

for (let i = 1; i <= N; i++) {
    const [time, pay] = input[i].split(" ").map(Number);
    T.push(time);
    P.push(pay);
}

for (let i = N - 1; i >= 0; i--) {
    if (i + T[i] <= N) {
        dp[i] = Math.max(dp[i + 1], dp[i + T[i]] + P[i]);
    } else {
        dp[i] = dp[i + 1];
    }
}

console.log(dp[0]);

 

💡시간복잡도

 

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

14501번을 수정하는 방식으로 진행하려고 했는데 방식이 달라 더 문제를 일으킴 

 

💡 다른 풀이 or 기억할정보

-