문제
풀이
요구사항
여러 과제가 주어지고 각 과제에는 점수와 마감일이 정해져있다. 마감일이 지난 과제의 점수는 받을 수 없다.
최대한 많은 점수를 받도록 하시오.
해결방안
가장 먼저 떠올릴 수 있는 방법은 점수가 높은 과제부터 처리해주도록 하는 방법이 있지만, 마감일까지 신경써줘야 하기 때문에 좀 더 개선시켜야 한다.
어떤 과제의 마감일이 d라고 했을 때, 1일 ~ d일까지는 해당 과제의 점수를 받을 수 있다.
과제를 가장 늦게 수행한다고 가정하고, 가장 점수가 높은 과제를 d일에 배정한다.
그리고 그 다음으로 점수가 높은 과제를 d일에 배정한다. 만약 d일에 이미 배정되어 있는 과제가 있다면 d-1일에 배정하고, d-1일에도 이미 배정되어 있는 과제가 있다면 d-2일에 배정하는식으로 진행하면 최대로 받을 수 있는 점수를 구할 수 있다.
문제에 나와있는 예시로 예를 들어보자.
4 60
4 40
1 20
2 50
3 30
4 10
6 5위와 같이 과제의 마감일과 점수가 주어졌을 때, 가장 점수가 높은 과제부터 처리해주기 위해 점수를 기준으로 내림차순 정렬을 수행해준다.
4 60
2 50
4 40
3 30
1 20
4 10
6 5그리고나서 첫 번째 과제를 특정 날짜에 배정해주기 위해 최대 마감일 만큼의 크기(6)를 가진 배열을 만들어 준다.
[0,0,0,0,0,0]값이 0인 인덱스는 아직 과제가 배정되어있지 않는 날을 의미하고, 편의를 위해 0번 인덱스를 1일이라고 가정하겠다.
가장 점수가 높은 과제는 마감일이 4일이고, 점수가 60점인 과제이기 때문에 이 과제를 배정해주면 배열은 아래와 같이 바뀐다.
[0,0,0,60,0,0]두 번째로 점수가 높은 과제(2, 50)도 배정해준다.
[0,50,0,60,0,0]세 번째도 과제(4, 40)도 배정해주려고 보니까 이미 4일에는 과제가 배정되어 있다. 따라서 4-1일을 확인한다.
4-1일에는 과제가 배정되어있지 않으므로 과제를 배정해준다.
[0,50,40,60,0,0]네 번째 과제(3, 30)도 배정하려고 보니까 3일에 이미 과제가 배정되어있으므로 아래와 같이 배정된다.
[30,50,40,60,0,0]다섯 번째 과제(1, 20)은 배정해줄 날짜가 없기 때문에 그냥 넘어간다.
여섯 번째 과제(4, 10)도 배정해줄 날짜가 없다.
일곱 번째 과제(6, 5)는 배정해줄 날짜가 있다.
[30,50,40,60,0,5]이렇게 모든 과제가 배정되었고, 이때의 점수를 모두 합하면 최대로 받을 수 있는 점수가 된다.
코드
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const arr = input.slice(1).map((e) => e.split(' ').map(Number));
// 점수를 기준으로 내림차순 정렬
arr.sort((a, b) => b[1] - a[1]);
const maxDay = arr.reduce((acc, cur) => Math.max(acc, cur[0]), 0);
const assignments = Array(maxDay + 1).fill(0);
let answer = 0;
for (let [d, w] of arr) {
// 해당 일자에 과제가 비어있다면 과제 배정
if (assignments[d] === 0) {
assignments[d] = w;
answer += w;
} else {
// 과제가 비어있지 않다면 하루씩 앞으로 이동하며 비어있는 날에 과제 배정
for (let i = d - 1; i >= 1; i--) {
if (assignments[i] === 0) {
assignments[i] = w;
answer += w;
break;
}
}
}
}
console.log(answer);
