tlov
1561 - 놀이 공원 본문
문제: boj.kr/1561
날짜: 9월 8일 (일)
성공여부: X [01:30:34]
이분탐색 문제이다.
N이 20억이고 M이 1만이기 때문에 0분에 아이들을 M개의 놀이기구에 태우고 1분마다 한 명씩 태울 수 있는 곳에 태워서 모든 경우의 수를 찾는건 시간초과이다. 그럼 이를 효율적으로 찾는 방법을 생각해야 하는데, 이때 시간을 이용해 이분탐색을 하면 모두를 태우는 최적의 시간을 약 31번만에 더 빠르게 찾을 수 있다는 것까지는 생각했다.
하지만, 이 매개변수를 찾는 방법과 찾아서 활용하는 방법을 생각하지 못해서 해설을 봤다.
22 5
1 2 3 4 5
22명을 태우는 상황이라면 22명이 모두 타는 최적의 시간을 찾는다. 이 시간을 찾는 방법은 0분에 M(5)명을 일단 태우고 0~30*n까지 이분탐색을 진행하면서 mid값에 각 놀이기구의 시간을 나눈 몫을 더해서 ㅡ이 부분이 이해하기 어려웠는데, 만약 놀이기구가 운행시간이 3분이라고 한다면 전체 6분동안은 2명을 태울 수 있고 9분동안은 3명을 태울 수 있다. 이를 몫으로 구할 수 있는 것이다.ㅡ M(5) + 몫의 전체 합이 n명보다 크거나 같으면 시간을 더 줄여보고, n(22)명보다 작으면 해당 시간에는 n(22)명이 다 못타는 것이니 시간을 더 늘려가면서 최적의 시간을 찾아본다.
위 예제에서 해당하는 값을 찾아보면 22명의 경우 8분이 나온다.
8 / 1 = 8
8 / 2 = 4
8 / 3 = 2
8 / 4 = 2
8 / 5 = 1
= 17 + 5 = 22
그럼 8분에서 모두 다 탈 수 있는 것이니까 해당 시간의 1분 전 상황을 구해서 타고있는 인원을 구한다음 8분의 상황에서 탈 수 있는 놀이기구에 남은 인원을 태워보면 마지막으로 타는 인원의 놀이기구 번호를 찾을 수 있다.
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
// 시간제한 2초, 메모리제한 128MB
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
long[] play = new long[m];
for (int i = 0; i < m; i++) play[i] = Integer.parseInt(st.nextToken());
if (n <= m) System.out.println(n);
else {
long low = 0;
long high = 30L * n + 1;
while (low + 1 < high) {
long mid = (low + high) / 2;
long cnt = m;
for (int i = 0; i < m; i++)
cnt += (mid / play[i]);
if (cnt >= n) high = mid;
else low = mid;
}
long ret = m;
for (int i = 0; i < m; i++)
ret += (low / play[i]);
for (int i = 0; i < m; i++) {
if (high % play[i] == 0) ret++;
if (ret == n) {
System.out.println(i+1);
break;
}
}
}
}
}
'알고리즘 문제' 카테고리의 다른 글
2098 - 외판원 순회 (2) | 2024.09.17 |
---|---|
2565 - 전깃줄 (0) | 2024.09.12 |
2156 - 포도주 시식 (0) | 2024.08.30 |
1463 - 1로 만들기 (0) | 2024.08.29 |
[swea] 1859. 백만 장자 프로젝트 (1) | 2024.08.28 |