Node.js)백준 1561번: 놀이공원

https://www.acmicpc.net/problem/1561

1561번: 놀이 공원

 

프로그래머스에서 입국심사를 풀어봤기 때문에 마지막 아이가 타게 된 시간은 이분탐색으로 쉽게 구할 수 있었다. 

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

 

문제는 그 아이가 도대체 어느 놀이기구에 타게 되는지 구하는 것인데. 

 

0.  아이들 수보다 놀이기구 개수가 많으면 그냥 아이들 수 만큼 출력하고 종료. 

 

1. 우선 이분탐색을 통해 마지막 아이가 놀이기구에 타게 되는 시간을 구함. 

 

2. 그 아이가 타게 되는 시간-1 을 해서 (시간-1)까지  아이들이 얼마나 탔는지 구함. 

 

3. 원래 시간으로 돌아와서. 그 때, 탈 수 있으면  ++  해주면서.. 그게  N이 되면 출력 

 

11명의 아이 5개의 놀이기구 [2,2,2,2,2] 이 있을 때, 굳이 계산하지 않아도 11번째 아이는 4분에 첫번째 놀이기구에 타게 되는 것을 알 수 있다. 

 

0초에, 아직 1분이 되기 전에 아이들이 우선 놀이 기구 탈 수 있는 만큼 쭉 빠진다. 

그래서 0분에 1,2,3,4,5번 아이들이 놀이기구를 타게 되고, 

0~2분 까지 놀이기구를 탈 것이다. 2분이 되면 싹 내리고, 6~10번 아이들이 탑승한다. 

그 아이들이 2~4분까지 타고,   4초에 11번이 탑승한다. 

 

아무튼 이분탐색을 통해 11번째 아이가 탑승하는 시간이 4분인 거를 구할 수 있고, 

 

11번째 아이가 어느 기구에 탈지를 정해야하는데. 그때 시간-1이 중요하다. 

4-1=3분까지 몇명의 아이가 탔는지 계산하고, 4분이 되었을 때, 타게 되는 아이들을 계산하는 것이다. 

 

솔직히 내가 써놓고도 뭔 말인지 모르겠다. 나중에 생각 정리되면 다시 작성해야할 것 같다. 

 

const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n").map(v => v.split(' ').map(Number))
const [N, M] = input[0];
const rides = input[1];
let min = 0;
let max = 60000000000;
let mid;
let time = Infinity;

if (N <= M) {
  process.exit(console.log(N));
}

while (min <= max) {

  mid = Math.floor((min + max) / 2);
  let temp = M;
  for (let i = 0; i < M; i++) {
    temp += Math.floor(mid / rides[i]);
  }
  if (temp >= N) {
    time = mid;
    max = mid - 1;
  } else {
    min = mid + 1;
  }
}

let temp = M;
for (let i = 0; i < M; i++) {
  temp += Math.floor((time - 1) / rides[i]);
}


for (let i = 0; i < M; i++) {
  if (time % rides[i] == 0) temp++;
  if (temp == N) {
    process.exit(console.log(i + 1))
  }
}