이분 탐색 문제라 좀 간단하게 풀릴 줄 알았는데, 고려해야하는 조건이 꽤 많아서 힘들게 풀었다.
먼저 일반적인 이분 탐색 문제와는 다르게 중간값을 key로 두고 비교하는 것이 아닌, 입력 길이를 중간값으로 나눠서 그 개수를 key로 두고 이분 탐색을 진행한다.
특히 조심해야할 부분은 자를 수 있는 최대 길이를 구해야 하고, 개수가 중복이 될 경우의 최대 길이를 찾아야 한다는 것!!
→ 예시로 807의 길이가 있으면, 170으로 잘라도 190으로 잘라도 모두 동일하게 4개의 개수로 자를 수 있다. 그렇다면 이 경우에서 상한값을 찾아야 하는 것! 그럼 답은 201씩 잘라야 하고, 이 부분을 구하기 위해서는 목표 개수(N)을 초과하는 첫 길이에서 -1을 해주면 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 이분 탐색
// 가능한 랜선길이 범위에서 탐색
class Main {
static int K, N;
static long[] cables;
static long answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
K = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
cables = new long[K];
long max = 0;
for (int i = 0; i < K; i++) {
cables[i] = Long.parseLong(br.readLine());
max = Math.max(max, cables[i]);
}
long min = 0;
long mid = 0;
answer = 0;
while (min < max) {
// 중간 값 구하기
mid = (min + max) / 2;
answer = 0;
// 중간 길이로 잘라서 몇개가 만들어지는지 구함
for (int i = 0; i < cables.length; i++) {
answer += (cables[i] / mid);
}
/*
[upper bound 형식]
mid 길이로 잘랐을 때의 개수가 만들고자 하는 랜선의 개수보자 작으면?
자르려고 하는 길이를 줄여야함 -> 최대 길이를 줄임
그 외에는 자르려고 하는 길이를 늘려야함 -> 최소 길이를 늘림
*/
if (answer < N) {
max = mid;
} else {
min = mid + 1;
}
}
System.out.println(min - 1);
}
}
Java
복사
그래서 처음에 이렇게 풀었는데, 틀렸다.
이유는, 만약 min, max 모두 값이 0이면 min < max 조건이 아니기에 이분 탐색을 수행하지 않게 된다.
그렇게 되면 upper bound는 0이 되어버리는데 실제로는 1이 나와야한다. 때문에, 0 ~ max가 아닌 0 ~ max + 1 범위에서 탐색하면 된다. 즉, 입력받는 범위에서 max + 1을 max값으로 잡아야 하는 것이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 이분 탐색
// 가능한 랜선길이 범위에서 탐색
class Main {
static int K, N;
static long[] cables;
static long answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
K = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
cables = new long[K];
long max = 0;
for (int i = 0; i < K; i++) {
cables[i] = Long.parseLong(br.readLine());
max = Math.max(max, cables[i]);
}
// upper bound를 수행하기 위해 최대 길이 + 1로 잡고 이분 탐색을 수행
max++;
long min = 0;
long mid = 0;
answer = 0;
while (min < max) {
// 중간 값 구하기
mid = (min + max) / 2;
answer = 0;
// 중간 길이로 잘라서 몇개가 만들어지는지 구함
for (int i = 0; i < cables.length; i++) {
answer += (cables[i] / mid);
}
/*
[upper bound 형식]
mid 길이로 잘랐을 때의 개수가 만들고자 하는 랜선의 개수보자 작으면?
자르려고 하는 길이를 줄여야함 -> 최대 길이를 줄임
그 외에는 자르려고 하는 길이를 늘려야함 -> 최소 길이를 늘림
*/
if (answer < N) {
max = mid;
} else {
min = mid + 1;
}
}
System.out.println(min - 1);
}
}
Java
복사