🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [head, ...tail] = fs.readFileSync(path).toString().trim().split('\n');
const answers = [0];
const T = [0];
const P = [0];
const N = Number(head);
for (const tp of tail) {
const [t, p] = tp.split(' ').map(Number);
T.push(t);
P.push(p);
}
const bt = (selected, total) => {
const pre = selected[selected.length - 1];
for (let i = pre + 1; i <= N; i++) {
if (i === N) {
const answer = T[i] === 1 && pre + T[pre] <= i ? total + P[i] : total;
answers.push(answer);
return;
}
if (pre + T[pre] <= i && i + T[i] - 1 <= N) {
bt([...selected, i], total + P[i]);
}
}
if (pre === N && T[pre] === 1) answers.push(total);
};
// 1. 순회 시작
for (let i = 1; i <= N; i++) {
if (i + T[i] - 1 <= N) {
bt([i], P[i]);
}
}
console.log(Math.max(...answers));🟢 풀이
⏰ 소요한 시간 : 1시간 30분
dp 문제 같았지만 적절한 점화식을 찾지 못했고, N의 범위가 작아 1부터 N까지 가능한 모든 조합으로 백트래킹을 수행해줄 수 있도록 풀이했다.
상담을 진행할 때(숫자를 선택할 때) 내가 상담을 온전히 진행할 수 있는지 확인해준다.
가장 마지막 포문을 보면 i는 1부터 N까지 상담할 날짜를 뽑는데, i번째 상담이 며칠동안 진행되는지 확인한 후 가능한 경우만 bt를 수행해주면 된다.
bt내부에서도 마찬가지로 내가 선택한 날짜 이후부터 N까지 또 다시 상담할 날짜를 뽑는데, 수행할 수 있는 날짜인지 확인한 뒤 백트래킹을 수행해주면 된다.
다만 가장 마지막 날짜에 상담이 진행 가능한데 이를 놓치게 되는 경우가 많아 여러번 조건을 수정해 주었고 4번에 시도끝에 맞았습니다를 받았다.
다만, 내가 놓친 부분을 찾기 위해 질문게시판의 여러 반례를 참고했고 실제 코딩테스트나 알고리즘 대회에서는 반례가 주어지는 경우가 없기 때문에 내 힘으로 풀었다고 할 수 없다.
그래서 유튜브를 참고해 dp의 풀이로도 풀어보았다.
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [head, ...tail] = fs.readFileSync(path).toString().trim().split('\n');
const N = Number(head);
const dp = new Array(N + 1).fill(0);
const T = [];
const P = [];
for (const tp of tail) {
const [t, p] = tp.split(' ').map(Number);
T.push(t);
P.push(p);
}
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]);유튜브의 풀이대로라면 이러한 문제는 역으로 푸는게 편리하다고 한다. 나도 여기까지는 생각이 뻗었으니 연습이 된다면 충분히 생각할만한 사고인듯..
아무튼 역으로 풀이를 진행하고, dp[i]은 i번째 상담 결정 시 최대 수익으로 정의한다.
그래서 내가 i번째날에 상담이 가능하다면, i번째 날은 상담을 하거나, 안하거나 결정할 수 있는데 내가 상담을 안했다면 dp[i+1]의 최대수익과 같을 것이고 상담을 했다면 dp[i+T[i]] + P[i]의 최대 수익과 같을 것이다. 따라서 두 가지 최대수익을 비교해 최대값으로 갱신해주면 된다.
만약 상담이 불가능 하다면 상담을 안한 dp[i+1] 의 값으로 갱신시켜 주면된다.
++) 참고로 유튜브에서 백트래킹으로 푸는 방법도 알려주는데 내 코드보다 훨씬 체계적이다. 아래는 유튜브를 보고 새롭게 작성한 백트래킹 풀이다. 진짜 너무 깔끔 bb. 아래로 풀게되면 이진 트리 형식으로 푸는건데 2의 50승 까지만 1초내로 풀이 가능하다고 한다. 따라서 N의 범위가 50보다 작을 경우에만 아래로 풀이 가능
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [head, ...tail] = fs.readFileSync(path).toString().trim().split('\n');
const answers = [];
const T = [];
const P = [];
const N = Number(head);
for (const tp of tail) {
const [t, p] = tp.split(' ').map(Number);
T.push(t);
P.push(p);
}
const bt = (pre, total) => {
if (pre >= N) {
answers.push(total);
return;
}
if (pre + T[pre] <= N) {
bt(pre + T[pre], total + P[pre]);
}
bt(pre + 1, total);
};
bt(0, 0);
console.log(Math.max(...answers));🔵 Ref
