Node.js) 백준 15486번: 퇴사 2

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

15486번: 퇴사 2

 

dp[i] 는 i일에 얻을 수 있는 최대 수익.

상담 종료일이 퇴사일 보다 늦는다면 상담할 수 없음
=> 뒤에서 부터 계산하기로 함.

위와 같은 이유로 상담을 못한다면.......
i일에 얻을 수 있는 최대 수익은 i+1일에 얻을 수 있는 최대 수익과 같음.
왜냐하면.. 어차피 내가 일하는 기간은 고정적이기 때문.

i일에 출근을 하든, 결근을 하든
적어도 그 다음날에 벌 수 있는 최대 금액은 벌 수 있다는 거임.

간단하게

i 1|2|3
T 1|1|1
P 1|1|1

이라고 했을때, 뒤에서부터 내가 돈을 얼마나 벌 수 있는지 생각해보면.

3일에 일을 해서 1을 얻을 수 있다고 했을 때...
최대 수익을 찾는 거니까..
2일에 무슨 일이 생겨서 출근을 안하던 최소한 3일에 번거
만큼은 벌 수 잇음.
그러니까

dp[i] = dp[i+1]

상담이 가능하면.
상담을 하는 경우, 하지 않는 경우. 두 가지 경우를 고려해야함. 
왜냐하면 어떤 날 상담을 하는 경우. 그 상담 기간이 길어진다면 
그 상담을 시작 하는 것이,  그 사이 다른 날 상담을 하는 것에 비해 손해일 수도 있기 때문

i 1|2| 3
T 1|2| 1
P 1|1|100

이렇게 2일에 일을 하면 3일에 일을 못해서 손해임.

그러니까 상담을 하는 경우. 안하는 경우를 고려해서
그 비용을 계산해서 돈을 많이 벌 수 있는 경우를 선택해야함.

일을 한다면.

work = P[i] + dp[i+T[i]]

그날 상담이 끝나고 바로 시작할 수 있는 상담일에서의 최대 수익을 더해야함.

일을 안한다면.
위에랑 똑같음. 다음날 얻을 수 있는 수익이 오늘 얻을 수 있는 수익의 최소값이 됨.

dp[i] = max(work, dp[i+1]);


초기값 dp[i] = 0;

 

 

const input = require('fs')
	.readFileSync('./dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.split(' ').map(Number));
const [N] = input.shift();

// console.log(input);
let dp = Array(N + 2).fill(0); // dp[i] 는 i일에 얻을 수 있는 최대 수익

for (let i = N; i > 0; i--) {
	if (input[i - 1][0] + i - 1 > N) {
		dp[i] = dp[i + 1];
	} else {
		const work = input[i - 1][1] + dp[input[i - 1][0] + i];
		const rest = dp[i + 1];
		dp[i] = Math.max(work, rest);
	}
}

console.log(dp[1]);