[백준] 2109 순회강연 (Javascript)

문제

BOJ2109_순회강연

풀이

문제 정의

n개의 대학이 있고 각각의 대학에는 d와 p라는 정보가 주어지는데, 이는 d일 안에 강연을 할 경우 p만큼의 강연료를 받는다는 것이다.
그리고 강연은 하루에 한 대학만 갈 수 있다.
따라서 강연의 총합을 최대치로 받도록 일정을 짜야한다.
이때 최대 얼마의 강연료를 받을 수 있는지 출력하는 문제다.

해결 방안

우선 단순한 생각부터 시작해보면 d일에 최대 강연료를 받을 수 있는 대학을 선택해서 가는 방법이다.

문제의 예시를 예로 들자면,

7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

1일차 -> 20
2일차 -> 100
3일차 -> 10
10일차 -> 50
20일차 -> 5
를 받으면 185로, 최대치를 받을 수 있다.

하지만 만약 아래와 같은 예시가 주어진다면 어떨까?

9
20 1
2 1
10 3
100 2
8 2
5 20
10 20
20 20
50 10

1일차 -> 20
2일차 -> 100
3일차 -> 10
10일차 -> 50
20일차 -> 20
이 되어 200이 된다.

하지만 실제로 받을 수 있는 강연료의 최대치는 200을 넘는다.
왜냐하면 20일 안에 가야하는 대학교가 3군데(5,10,20) 있는데 이는 "20일 전까지만 가면 되기 때문에" 꼭 20일이 아니더라도 19일 18일에도 방문할 수 있다.

1일차 -> 20
2일차 -> 100
3일차 -> 10
10일차 -> 50
18일차 -> 5
19일차 -> 10
20일차 -> 20

따라서 실제로는 위와 같이 일정을 짰을 때 215로 강연료를 최대로 받을 수 있다.

이 문제와 유사한 문제를 전에도 포스팅한 적이 있다.
아래 링크로 들어가면 풀이 과정을 확인할 수 있다.

[백준] 13904_과제 (with Node.js)

간단히 말하자면 [d,p] 쌍을 강연료(p)를 기준으로 내림차순 정렬시키고

100 2
50 10
20 1
20 20
10 3
10 20
8 2
5 20
2 1

최대 날짜+1 만큼의 길이를 가진 배열(days)을 만들어서 날짜와 인덱스를 일치시켜준다.
(아래 배열에서는 이해를 돕기 위해 첫 번째 원소의 인덱스를 1이라고 가정한다.)

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

그리고 정렬된 [d,p] 쌍을 순서대로 돌면서 days[d]===0이라면 days[d]에 p를 저장해준다.
이는 d일에 p만큼의 강연료를 받는다는 의미이고, 만약 0이 아니라면 d-1 ~ 1까지 1씩 감소시켜가며 0인 곳을 찾아서 p를 저장해준다.

[20, 100, 10, 0, 0, 0, 0, 0, 0, 50,
0, 0, 0, 0, 0, 0, 0, 5, 10, 20]

이러면 강연료가 큰 순서대로 정렬했기 때문에 강연료가 큰 대학부터 일정에 들어가고, d일에 이미 일정이 있다면 d일 안의 다른 날에 강연을 가게 일정을 계획함으로써 강연료를 최대로 받을 수 있는 일정을 짤 수 있다.

일정을 전부 작성했으면 days배열에 저장된 값을 전부 더해주어 최대 강연료를 구할 수 있다.

코드

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 pd = [];
let maxDay = 0;
for (let i = 1; i <= n; i++) {
    const [pay, day] = input[i].split(' ').map(Number);
    pd.push([pay, day]);
    maxDay = Math.max(maxDay, day);
}
// 강연료 내림차순 정렬
pd.sort((a, b) => b[0] - a[0]);

const days = Array(maxDay + 1).fill(0);
for (let [pay, day] of pd) {
    if (days[day] === 0) days[day] = pay;
    else {
        for (let i = day - 1; i >= 1; i--) {
            if (days[i] === 0) {
                days[i] = pay;
                break;
            }
        }
    }
}

console.log(days.reduce((acc, cur) => acc + cur, 0));