[BAEKJOON] 백준 24041: 성싶당 밀키트 (node.js)

문제 링크: https://www.acmicpc.net/problem/24041

24041번: 성싶당 밀키트

---

 

성싶당 밀키트 문제

예제

---

풀이

시간이 지나며 세균이 증식을 할 때, 제한된 균수 이하로 밀키트를 구매일로 부터 며칠 후 까지 먹을 수 있는 계산하는 문제이다. (무슨 이런..). 조건의 제한을 확인했을 때 부패속도 S1은 최대 10^9이며, 구매 후 최대 10^9까지 먹을 수 있기 때문에, 최대 균 수는 10^9 *2가 될 수 있다. 제한된 균 수를 확인하는 과정에서, 모든 균 수마다 비교를 한다면 시간초과가 날 것이기 때문에, 해당 과정에서 효율적인 이분 탐색방법을 사용할 필요가 있다고 생각했다.

이후 풀이 과정은 다음과 같다.

1. 필수인 0과 필수가 아닌 1을 기준으로 [부패속도, 유통기한]을 서로 다른 배열에 저장한다.
2. 이분 탐색을 통해 중앙 값을 잡고, 해당 중앙 값을 최대 세균 수로 가정하여 밀키트의 해당일의 세균수를 확인한다.
3. 해당 날짜와 K개의 자료를 뺀 최소 세균 수를 구한다. 단 0은 필수 재료이므로 세균의 증식 값을 반드시 추가하고, 1일 경우 세균 수가 가장 큰 재료 순으로 정렬하여 K개의 재료를 빼버린 후 나머지를 포함한다.
4. while 문을 통해 가장 최대 값을 구하기 위해 반복한다.

구현

/**
 * 유형: 이분탐색, 그리디
 */
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

function solution(n, g, k, foods) {
  let answer = 0;
  const info = { 0: [], 1: [] };
  // 0과 1 중요도에 따라서 각각 다른 배열로 저장
  for (let i = 0; i < n; i++) {
    const [s, l, o] = foods[i];
    info[o].push([s, l]);
  }

  // 해당 날짜와 K개의 재료를 뺀 최소 세균 수
  const getGermCount = (mid) => {
    let result = 0;
    // 0인 재료는 무조건 포함
    for (const [speed, limit] of info[0]) {
      result += speed * Math.max(1, mid - limit);
    }
    // 세균수로 정렬해서 세균 수가 가장 큰 재료 K개를 뺀 나머지를 포함
    info[1].sort((a, b) => {
      const gA = a[0] * Math.max(1, mid - a[1]);
      const gB = b[0] * Math.max(1, mid - b[1]);
      return gB - gA;
    });
    for (let i = k; i < info[1].length; i++) {
      const [speed, limit] = info[1][i];
      result += speed * Math.max(1, mid - limit);
    }
    return result;
  };

  let left = 0,
    right = 2e9;

  while (left <= right) {
    const mid = ((left + right) / 2) >> 0;
    const germs = getGermCount(mid);
    if (germs <= g) {
      answer = mid;
      left = mid + 1;
    } else right = mid - 1;
  }
  return answer;
}

const [N, G, K] = input[0].split(" ").map(Number);
const foodInformation = input.slice(1).map((i) => i.split(" ").map(Number));

console.log(solution(N, G, K, foodInformation));