[백준] 18234_당근 훔쳐 먹기 (Javascript)

문제

BOJ18234_당근 훔쳐 먹기

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
let [N, T] = input[0].split(' ').map(Number);
const carrots = input.slice(1).map((e) => e.split(' ').map(Number));
// w + p * T기준으로 내림차순 정렬
// 가장 기댓값이 큰 당근이 맨 앞으로 오고, 그 당근을 T-1일에 먹으면 됨
carrots.sort((a, b) => b[0] + b[1] * T - (a[0] + a[1] * T));
const answer = carrots.reduce((acc, cur) => (acc += cur[0] + cur[1] * --T), 0);
console.log(answer);

코드 풀이

우선 문제를 이해해보자.
오리는 N종류의 당근을 T일동안 재배할 것이다.
N$_i$ 당근의 초기맛은 W$_i$이고, 하루 지날때 마다 영양제를 주어 P$_i$만큼 맛이 증가한다.
토끼는 하루에 당근을 하나만 먹거나, 아예 안먹거나 둘 중에 하나를 고를 수 있고, T일이 되었을 때 먹은 당근의 맛이 최대치가 되도록 해야한다.

만약 P$_i$가 큰 당근이라면 하루가 지날수록 당근의 맛은 날이 갈수록 P$_i$만큼 증가하니 나중에 먹는게 이득일 것이다.
이를 식으로 세워보면 아래와 같다.

max$(W_i + P_i \times T-1)$ 을 T일에 먹고, N$_i$는 리스트에서 제거
max$(W_i + P_i \times T-2)$ 를 T-1일에 먹고 N$_i$는 리스트에서 제거
.
.
.
max$(W_i + P_i \times 0)$ 를 T-T+1 일에 먹는다.

이렇게 하면 T까지 먹은 당근의 맛의 합의 최대치를 구할 수 있다.

하지만 $T\le100,000,000$ 이고 시간 제한은 1초이기 때문에 이런 방식으로는 시간 초과가 발생할 우려가 있다.

따라서 다른 방식을 찾아봐야 한다.

모든 당근들을 $W_i+P_i\times T$ 가 큰 순으로 내림차순 정렬을 하여 이렇게 정렬된 배열을 이용하면 모든 당근의 개수만큼만 순회하면 되기 때문에 더 빠른 시간내에 찾을 수 있다.

정렬된 배열을 처음부터 순회하며 $W_i+P_i\times T$ 이 공식을 적용시면서 결괏값을 누적시키면 된다. 이때 T를 1씩 줄여가면서 공식을 적용시켜주면 되는데, 첫날에는 당근에 영양제를 주지 않으니 T를 먼저 1 줄이고 연산을 시작하면 된다.