1561

문제풀이

n명의 아이들이 운행시간이 정해진 m종류의 1인승 놀이기구를 순서대로 탈 때 마지막 아이가 타게 되는 놀이기구의 번호를 구해야 한다. x분일 때 가장 n명에 가깝게 태울 수 있는지를 이분탐색으로 탐색한 다음 x + 1분 일 때 n명이 몇번째 놀이기구를 타는지를 구할 수 있다.

입력

• n, m: n명의 아이들과 m개의 놀이기구
• m 개의 놀이기구의 운행시간

로직

1. 입력을 받는다.
2. 최소값 0과 최대값 2억명 x 30분을 정의한다.
3. n에 가장 가까운 아이 수를 저장할 변수를 선언한다.
4. 이분탐색을 수행한다.
   1. mid분 일 때 n 보다 많은 아이를 태우면 더 적은 시간을 확인하기 위해 최대값을 갱신한다.
   2. n보다 작으면 (3)에서 선언한 변수를 갱신하고 가장 n에 가까운 아이를 태울 때까지 최소값을 갱신한다.
5. n에 가장 가까운 아이 수를 태우는게 mid 분이다.
6. 시간이 mid + 1분 일때 (3)에서 선언한 변수가 n이 될 때 몇번째 놀이기구인지 찾아서 반환한다.

22 5
1 2 3 4 5

입력값이 위와 같을 때

• 15분
  놀이기구를 15분 동안 운행하면 1번 15명, 2번 7명, 3번 4명, 4번 3명, 5번 3명으로 32명과 처음에 비어있을 때 태우는 5명을 더해서 총 37명을 태울 수 있다. 태워야하는 22명 보다 많은 아이를 태우기 때문에 더 적은 운행시간을 확인해 볼 수 있다.

• 10분
  놀이기구를 10분 동안 운행하면 1번 10명, 2번 5명, 3번 3명, 4번 2명, 5명 2명으로 22명과 처음에 비어있을 때 태우는 5명을 더해서 총 27명을 태울 수 있다. 태워야하는 22명 보다 많은 아이를 태우기 때문에 더 적은 운행시간을 확인해 볼 수 있다.

• 5분
  놀이기구를 5분 동안 운행하면 1번 5명, 2번 2명, 3분 1명, 4분 1명, 5분 1명으로 10명과 처음에 비어있을 때 태우는 5명을 더해서 총 15명을 태울 수 있다. 태워야하는 22명 보다 적은 아이를 태우지만 가장 가까운 수는 아닐 수 있으니 더 많은 운행 시간을 확인 해본다.

• 7분
  놀이기구를 7분 동안 운행하면 1번 7명, 2번 3명, 3번 2명, 4번 1명, 5번 1명으로 14명과 처음에 비어있을 때 태우는 5명을 더해서 총 19명을 태울 수 있다. 22번째 아이까지 3명 남았으니 세어 볼 수 있다.

• 8분
  8분째에 20번째 아이는 1번 놀이기구를 타고 21번째는 아이는 2번 놀이기구를 타고 22번째 아이는 4번 놀이기구를 탄다.

그래서 답은 4가 된다.

맞왜틀

• 최대 값의 범위를 잘못 지정하면 오답이 된다.

리팩토링