BOJ 1561번 놀이공원 자바(java) 풀이
문제정리
- 놀이공원에는 총 M개의 1인승 놀이기구가 있다.
- 기구에는 1~N까지 번호가 매겨져 있다.
- 모든 놀이기구에는 운행시간이 정해져 있어, 시간이 지나면 내려야 한다.
- 놀이기구가 비어있으면 가장 앞에 서 있는 아이가 탑승한다.
- 여러 놀이기구가 비어있다면 더 적은 번호의 놀이기구를 탑승한다.
- 줄의 마지막 아이가 타게 되는 놀이기구 번호를 구하여라!
문제 풀이
이 문제는 대충 입력의 크기만 봐도 시뮬레이션으로 구현할 수 없습니다.
이는 x분에 몇명의 아이들까지 놀이기구를 타는지 계산하여 문제를 해결하여야 합니다.
- 마지막 사람이 타기전 시간이 몇분인지 이분탐색을 통해 알아내고 그 시간까지 몇명의 사람이 탔는지 계산합니다.
- 그러면 마지막 시간에 몇명이 더 타야하는지 알 수 있습니다( n - child)
- 앞의 놀이기구 부터 1분 사이에 사람이 더 탈 수 있는지 체크하여 count하고 남은 사람이 모두 타면 그때의 index를 출력합니다.
예를들어 놀이기구의 running time이 1 2 3 4 5 라면
7분때는 7 + 3 + 2 + 1 + 1 + 5(처음 5명) = 19명이 탔습니다
8분때는 8 + 4 + 2 + 2 + 1 + 5(처음 5명) = 22명이 탑니다
두개를 비교해보면 1번 놀이 기구, 2번, 4번 놀이기구에 한명씩 더 탔습니다.
즉 4번 놀이기구에 22번째 사람이 탔으므로 마지막 사람이 탄 놀이기구는 '4'가 됩니다.
이를 몪의 변화가 있는지 없는지로 판단하여 사람이 1분 사이에 그 놀이기구를 탔는지 안 탔는지 판단할 수 있습니다.
이분 탐색
- left=0, right = 600억으로 잡습니다.
왜냐하면 최대 20억명의 어린이가 있을 수 있고 러닝 타임은 최대 30분 입니다. 놀이기구가 한대라면 모두 타는데 최대 600억 분의 시간이 걸립니다
- 중간 시간을 구해서 running time 만큼 나눠서 시간안에 그 놀이기구에 몇명이 탈 수 있는지 구해서 모두 구합니다.
그래서 그 인원이 인원수 n 보다 크다면 왼쪽 범위에서 탐색.
인원수 n 보다 작다면 오른쪽 범위에서 탐색합니다.
백준 1561번 놀이공원 자바(java) 소스코드