[백준] 1561번, 놀이 공원(JavaScript)

Algorithm

문제 정보 : 놀이 공원

• 문제 분류 : 알고리즘 연습 중급 1/3, 이분탐색 (연습)
• 문제 출처 : 백준 골드 2, 놀이 공원

시작하며 ✅

이분 탐색의 기준으로 시간을 선택해야하는데 이 방법을 생각하지 못해서 어려웠다..

접근 과정

이분탐색 단원의 문제이므로 당연히 이분탐색을 써야한다고 생각하고 접근했었다. 하지만 놀이기구들의 시간을 보면서 최소공배수를 이용해서 이분탐색을 해볼까 했지만 불가능하다는 걸 깨닫고 다른 방식으로 접근했다.
시간이라는 키워드를 생각해냈지만 끝네 해당 시간까지 놀이기구를 탄 인원수를 이분탐색을 해야한다는 것을 생각하지 못하고 결국 다른 분들의 풀이를 참고하여 풀었다.

풀이 과정 ✨

1. 조건(특정 수(mid)보다 작은 숫자의 개수가 >= k)을 만족하는 경우를 찾기 위한 이분탐색을 진행했다.
2. mid 보다 작은 경우의 수를 구하기 위해 mid / 행의 번호의 결과값들을 모두 카운트 해주고 이를 통해 조건을 확인했다.
   2-1. 단, mid / 행의 번호 결과가 행의 수(N) 보다 커지는 경우 결과값을 N으로 수정해주었다.

코드 (시간초과 풀이)

// const readFileSyncAddress = '/dev/stdin';
const readFileSyncAddress = "text.txt";

let input = require("fs")
  .readFileSync(readFileSyncAddress)
  .toString()
  .split("\n");

const [N, M] = input[0].split(" ").map(Number);
const nums = input[1].split(" ").map(Number);

// 예외 : 아이들의 수가 놀이기구 수보다 작을 경우.
if (N < M) {
  console.log(N);
  return;
}

const max = Math.max.apply(null, nums);

let answer = 0;
let start = 0;
let end = max * N;

let minTime = Infinity;

while (start <= end) {
  const mid = Math.floor((start + end) / 2);

  let cnt = M;

  nums.forEach((n) => {
    cnt += Math.floor(mid / n);
  });

  if (cnt >= N) {
    minTime = Math.min(minTime, mid);
    end = mid - 1;
  } else {
    start = mid + 1;
  }
}

let prevCnt = M;
nums.forEach((n) => {
  prevCnt += Math.floor((minTime - 1) / n);
});

for (let i = 0; i < M; i++) {
  if (minTime % nums[i] === 0) {
    prevCnt++;
  }

  if (prevCnt === N) {
    answer = i + 1;
    break;
  }
}

console.log(answer);

마치며 🚩

어려운 문제였다.. 이분탐색 문제라는 것을 파악하지 못했고.. 문제 접근 방법 또한 스스로 찾지 못했다. 더 많은 문제를 풀어보며 감을 익혀야겠다.