- Today
- Yesterday
- Total
메이쁘
(JAVA) 백준 1561번 : 놀이 공원 --- [이분탐색] 본문
1561번: 놀이 공원
첫째 줄에 N(1<= N<= 2,000,000,000)과 M(1<= M<= 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 이하��
www.acmicpc.net
안녕하세요.
이분탐색 문제 입니다.
역시 이분탐색답게
오름차순으로 쭉 정렬하는 배열의 index와 value 선정이 어려웠습니다.
어떤 기준으로 쭉 나열해서 이분탐색해야 정답을 얻을 쑤 있을까?
가 이분탐색의 풀이 핵심같습니다.
저도 해설 참고했습니다..ㅠㅠ
이분탐색을 위한 배열의 기준은
"index 분이 되었을 때, 총 몇 명이 탈 수 있는지" 입니다.
즉, index : x분 /// value : x분까지 탈 수 있는 인원의 수 인 셈이죠.
start는 0분
end는 (n명 / m개 놀이기구) * 놀이기구 중 최대 운행 시간 이 됩니다.
이렇게 해서 이분탐색을 시작합니다.
value를 구하기 위해서는 놀이기구 하나하나 for문 탐색하면서
현재까지 해당 놀이기구에 탈 수 있는 인원 = 지금까지 지난 시간 / 해당(index) 놀이기구의 운행 시간
을 계산해서 총 누적 인원을 얻습니다.
이 누적 인원과 n을 비교하면서 이분탐색하는거죠.
그렇게 하다 n 이상이고, 가장 n과 가까운 지점을 얻은 후
이 지점과 이 지점-1 지점을 비교하면서 다른 값을 count합니다.
*** 이 때, 이분탐색으로 얻은 지점에서의 총 인원 - n 을 통해 그 사이에 n번 째 인원이 탑승하는 놀이기구를 파악할 수 있습니다.
간단하죠?
자세한 설명은 아래 소스코드를 참고하시기 바랍니다.
감사합니다!
소스코드
'Algorithm > Baekjoon' 카테고리의 다른 글
| (JAVA) 백준 3197번 : 백조의 호수 --- [BFS] (0) | 2020.10.03 |
|---|---|
| (JAVA) 백준 16197번 : 두 동전 --- [백트래킹] (0) | 2020.10.02 |
| (JAVA) 백준 2842번 : 집배원 한상덕 --- [BFS, 투 포인터] (1) | 2020.09.26 |
| (JAVA) 백준 1717번 : 집합의 표현 --- [Disjoint-Set] (0) | 2020.09.25 |
| (JAVA) 백준 3109번 : 빵집 --- [그리디, 백트래킹, DP] (0) | 2020.09.25 |