2109 순회 강연 (자바스크립트)

문제

한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.

예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

입력

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

출력

첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

=====

문제 풀이

이 문제에서 주의할 점은 day 안으로 강연을 하면 된다는 것이다.

만약 [price,day] 가 [100,3], [200,3] 와 같이 주어졌다면 200원이 100원 강연보다 비싸므로 200원 강연만 하게 되어 정답은 200이 출력된다 가 아니라 3일 안으로만 강연을 하면 되는 거니까 3일 차에 200원 강연하고, 2일 차에 100원 강연을 한다면 결국 정답은 300원이 된다는 것이다. 이것을 토대로 코드 로직을 세워보면 우선 강연료가 비싼 것들을 마감 날에 처리하고 나머지 강연을 비는 스케줄에 진행하면 된다. 이것을 위한 로직은 아래로 정리했다.

1. 가격을 기준으로 내림차순 정렬

2. 가격이 높은 요소부터 꺼내 보면서 그 강연의 마감 날짜가 아직 기록되지 않았다면 기록해주기

3. 만약 기록 된 날들보다 더 작은 날이라면 최장 강연 날짜와 현재 강연의 마감날짜 중 작은 날부터 기록을 검토해보면서 기록되지 않은 날에 강연 스케줄 넣어준다.

아래는 가격을 기준으로 내림차순 정렬

const arr = input
    .slice(1)
    .map((v) => v.split(' ').map(Number))
    .sort((a, b) => {
        return b[0] - a[0];
    });

현재까지의 스케줄보다 더 뒤의 day라면 해당 day에 강연 등록 시켜주고,

그렇지 않다면 빈 강의에 강연 등록시켜주기

const obj = {};

while (arr.length) {
    const [price, day] = arr.shift();
    const MAX_DAY = Math.max(...Object.keys(obj));
    if (day > MAX_DAY) {
        obj[day] = price;
    } else {
        for (let d = Math.min(MAX_DAY, day); d > 0; d--) {
            if (!obj[d]) {
                obj[d] = price;
                break;
            }
        }
    }
}

기록을 방문해가면서 비용 계산

console.log(Object.keys(obj).reduce((acc, cur) => acc + obj[cur], 0));

정답 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const arr = input
    .slice(1)
    .map((v) => v.split(' ').map(Number))
    .sort((a, b) => {
        return b[0] - a[0];
    });
const obj = {};

while (arr.length) {
    const [price, day] = arr.shift();
    const MAX_DAY = Math.max(...Object.keys(obj));
    if (day > MAX_DAY) {
        obj[day] = price;
    } else {
        for (let d = Math.min(MAX_DAY, day); d > 0; d--) {
            if (!obj[d]) {
                obj[d] = price;
                break;
            }
        }
    }
}

console.log(Object.keys(obj).reduce((acc, cur) => acc + obj[cur], 0));

 

 

console.log (object.keys (obj) .reduce ((Acc, cur) => acc + obj [cur], 0);