퇴사

문제

• 백준 14501번 - 퇴사

언어

• JavaScript

문제 풀이 step 1

• 백준 15650번 - N과 M (2) 풀이 에서 풀었던 방식을 이용해서 풀 수 있습니다.
• 1 ~ N 일까지 하루씩 늘려가면서 당일의 일을 할지, 하지 않을지를 결정하면서 모든 경우를 확인해보면 됩니다.
• 재귀 호출의 구조에 따라서 나눠보겠습니다.
  1. 불가능한 경우
     • 당일의 일을 하는데 퇴사 날짜인 N + 1 일을 넘어가는 경우
  2. 정답을 찾는 경우
     • 일을 하다가 퇴사 날짜인 N + 1 일이 되는 경우
  3. 다음 경우 호출
     • 아직 퇴사 날짜인 N + 1 일이 되지 않은 경우
• 기존의 1 씩 늘려가면서 선택 할지, 안할지를 고려하는 문제와는 약간 다릅니다. 이 문제에서는 선택을 할 경우에는 다음 경우가 상담에 걸리는 날짜 만큼 늘린 날짜가 되기 때문입니다.

시행 착오 (삽질)

• 재귀의 구조 중에서 불가능한 경우와 정답을 찾는 경우를 구현하는데 날짜를 잘못 구현하는 바람에 삽질을 조금 했습니다.
• 굳이 세세하게 조건을 만들어줄 필요가 없었습니다. 기존에 하던데로 depth === n 또는 depth === n + 1 과 같이 하면 되었습니다.
• 아무래도 이 문제는 선택할 경우 1 이 늘어나는 것이 아닌 상담에 걸리는 시간만큼 늘어나기 때문에 헷갈렸던 것 같습니다.
• 정답을 찾는 경우에서의 time <= n && time + t[time] > n + 1 과 같은 조건은 어차피 선택하지 않는 경우를 통해서 time === n + 1 에서 잡히게 되어있습니다.
• 오히려 time <= n && time + t[time] > n + 1 과 같이 하면 고려하지 않는 경우가 생겨서 모든 경우를 확인할 수 없습니다.

소스 코드 1

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

let max = 0;

const rec = (n, t, p, time, pay) => {
	if (time === n + 1) {
		max = Math.max(max, pay);
		return;
	}

	if (time > n + 1) return;

	// 당일의 일을 하는 경우
	rec(n, t, p, time + t[time], pay + p[time]);

	// 당일의 일을 하지 않는 경우 내일로 넘어감
	rec(n, t, p, time + 1, pay);
};

const solution = (input) => {
	const n = parseInt(input[0]);

	// 1일 부터 시작하기 위해 0 번 index 에는 null 값을 넣어놓는다.
	const t = [null];
	const p = [null];
	for (let i = 1; i < n + 1; i++) {
		[t[i], p[i]] = input[i].split(" ").map(Number);
	}

	rec(n, t, p, 1, 0);

	return max;
};

console.log(solution(input));