[백준 / javascript] 13458번 시험감독

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

처음에 각 시험장의 응시생 수(a)에서 총 감독관이 감독할 수 있는 응시생의 수(b)를 빼고 남은 응시생의 수를 또 부감독관이 감독할 수 있는 응시생의 수(c)로 빼서 합걔를 구하려고 했더니 백준에서 시간초과가 발생했다.

• 시간초과가 발생한 코드

const readFile = '/dev/stdin';

const input = require('fs')
  .readFileSync(readFile)
  .toString()
  .trim()
  .split('\n');

const [n, people, supervisor] = input;
const [b, c] = supervisor.split(' ').map((i) => Number(i));
const a = people.split(' ');

let cnt = 0;
for (let i = 0; i < a.length; i++) {
  a[i] = a[i] - b;
  cnt += 1;
  while (a[i] > 0) {
    a[i] = a[i] - c;
    cnt += 1;
  }
}
console.log(cnt);

구글링을 통해 다른 풀이를 찾아봤더니 아예 다른 방식의 풀이가 있었다.

1. 시험장 인원 - 총감독관(이 관리할 수 있는 응시자 수)가 0보다 작은 경우, 총감독 혼자서 관리할 수 있으므로 sum에 1을 추가한다.
2. 필요한 부감독관은 (응시자 - 총감독관) / 부감독관을 내림한 값의 +1을 해주면 된다. 나머지가 0일 경우 +1을 해주지 않는다.
3. 부감독관이 필요할 때는 무조건 총감독관이 1명 있을 때이므로 따로 +1을 해줘야 한다.

이 방식대로 구현했더니 시간초과가 발생하지 않고 정답처리 되었다.

• 정답 코드

const readFile = '/dev/stdin';

const input = require('fs')
  .readFileSync(readFile)
  .toString()
  .trim()
  .split('\n');

const [n, people, supervisor] = input;
const [b, c] = supervisor.split(' ').map((i) => Number(i));
const a = people.split(' ');

let result = 0;
for (let i = 0; i < n; i++) {
  // 필요한 부감독관
  const admin = Math.floor((a[i] - b) / c);
  // 총 감독관이 1명만 필요한 경우
  if (a[i] <= b) {
    result += 1;
  } else {
    // 나머지가 있는 경우와 없는 경우 나누기
    result += (a[i] - b) % c === 0 ? admin + 1 : admin + 2;
  }
}
console.log(result);

참고

https://punctum.world/algorithm/BOJ13458/