문제

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

문제가 정말 길지만 짧게 줄여보면 N개의 일과 T라는 시간이 있을때,
큐를 사용해T라는 시간동안 N개의 일중 몇개를 할 수 있는지 알아내는 문제다.

풀이방법

문제에서 큐(Queue)를 사용한다고 적혀있다.
그래서 일할 수 있는 시간 동안 몇 개의 일을 처리할 수 있는지 알아볼 개수가 있는 배열을
누적합으로 값을 더해주면 i번째 일까지 처리했을때 시간이 얼마나 걸리는지 알수있다.
그 후에 누적합을 탐색하며 일할수 있는 시간보다 i번째 값이 크면 탈출해 i-1을 리턴한다.

하지만 이렇게 하면 무조건 시간초과가 날수밖에 없다.
일의 개수 N의 최대값이 10,000인데 일할수 있는 시간이 2×109이기 때문에
2x1013의 시간 = 대충 200,000,000,000,000번을 탐색하며 제한시간 1초는 가뿐하게 넘긴다.

그래서 탐색할땐 이진탐색으로 탐색하다가 찾은곳의 결과가 찾으려는 결과보다 큰경우에는
1을 빼서 리턴해주면 된다.

코드

const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync(0, 'utf-8')
    : fs.readFileSync(__dirname + '/input.txt').toString()
)
  .trim()
  .split('\n');
const input = (() => {
  let line = 0;
  return () => stdin[line++].split(' ').map(v => +v);
})();

const solution = () => {
  const [N, M] = input();
  const todos = input();
  const times = Array.from({ length: M }, () => +input());
  // 누적합
  const dp = [todos[0]];
  let result = '';

  // 이진탐색으로 위치를 찾는다.
  const findIdx = findVal => {
    let left = 0;
    let right = dp.length - 1;
    let mid = 0;

    while (left <= right) {
      mid = Math.floor((left + right) / 2);

      if (findVal === dp[mid]) {
        break;
      } else if (findVal <= dp[mid]) {
        right = mid - 1;
      } else if (findVal > dp[mid]) {
        left = mid + 1;
      }
    }
    if (dp[mid] > findVal) mid--;
    return mid + 1;
  };

  // 누적합을 구한다.
  for (let i = 1; i < todos.length; i++) {
    dp[i] = dp[i - 1] + todos[i];
  }

  times.forEach(time => {
    result += `${findIdx(time)}\n`;
  });

  return result;
};

console.log(solution());