지난 포스트에 이어서 Parametric Search 문제를 풀어보겠다.
오늘의 문제는 BOJ 1654 랜선 자르기(S2)!
접근
자 일단,, 이 문제 어제 풀었던 나무 자르기랑 비슷하다.
다른 점이 있다면 나무를 자를 땐 뺄셈 연산을 사용했지만 이번엔 나눗셈 연산을 사용한다는거,,
그리고 어제 얘기했던 그 Overflow 문제까지 더해져서 아주 다 풀어놓고 방문 긁는 치와와처럼 아르르륽ㄹ그륵ㄺ 하면서 성질낸 그런 문제였다.
어제 했던대로 Parametric Search의 정의에 맞춰 어떻게 해결할지 고민해보자.
이산적인 입력이 들어왔을 때 최적값을 구하는 문제를 예-아니오 답이 있는 질문으로 바꿔 푸는 알고리즘
- 이산적인 입력이 들어왔을 때 : 랜선의 길이로 구성된 배열은 이산적인, 셀 수 있는 입력이다.
- 최적값을 구하는 문제를 : 우리가 구하고 싶은 건 원래 가지고 있던 랜선을 잘라서 마음 먹은 수 이상의 랜선은 얻을 수 있되, 가능하면 길게 잘라내고 싶은 것이다.
- 예-아니오 답이 있는 질문으로 바꿔 푸는 문제 : 문제에서 예-아니오로 판단해야 하는 명제는 '가지고 있는 랜선들을 같은 길이로 잘랐을 때 마음 먹은만큼 랜선을 얻어갈 수 있다.'이므로, 여기에 '예'로 대답할 수 있는 매개 변수를 이분 탐색하여 찾아 나가면 된다.
구현
햐 이거,, 굉장히 많이 배운 문제다. 일단 틀렸던 코드부터 보자.
상상도 못한 Overflow ㄴㅇㄱ
public static void main(String[] args) throws Exception {
st = new StringTokenizer(in.readLine());
// 랜선의 개수 [1, 10,000]
final int NUM_OF_CABLES = Integer.parseInt(st.nextToken());
// 필요한 랜선의 수 [1, 1,000,000] (NUM_OF_CABLES <= REQUIRED_CABLES)
final int REQUIRED_CABLES = Integer.parseInt(st.nextToken());
// 가지고 있는 랜선의 길이들 (자연수)
int[] lengthOf = new int[NUM_OF_CABLES];
for (int cable = 0; cable < NUM_OF_CABLES; cable++) {
lengthOf[cable] = Integer.parseInt(in.readLine());
}
// 이분 탐색을 위한 정렬
Arrays.sort(lengthOf);
long maxLength = Long.MIN_VALUE;
int low = 0;
int high = lengthOf[NUM_OF_CABLES - 1] + 1;
while (low <= high) {
int candidateLength = (low + high) >> 1;
long cableCnt = 0;
for (int cable = getLowerBound(lengthOf, candidateLength); cable < NUM_OF_CABLES; cable++) {
cableCnt += (lengthOf[cable] / candidateLength);
}
if (cableCnt >= REQUIRED_CABLES) {
maxLength = candidateLength;
low = candidateLength + 1;
} else {
high = candidateLength - 1;
}
}
System.out.println(maxLength);
}어제 본 그 틀과 정말 거~~의 똑같은데, 딱 한 줄 다르다.
cableCnt += (lengthOf[cable] / candidateLength);우리가 찾아야 할 최적해는 랜선을 잘라냈을 때 원하는 만큼 랜선을 얻어낼 수 있으면서 가능한 길게 자를 수 있는 길이를 얻는 것이므로, 잘라낼 단위 길이를 candidateLength라 놓고 나눗셈 연산을 했다.
그런데 여기서 계속 에러가 나서,,, 한참 골머리 썩다가 안되겠다 싶어서 질문 게시판에 들어가 봤더니 글쎄 high에서 Overflow가 터진게 문제였다.
사실 생각해보면 당연한게 문제에선 그냥 랜선의 최대 길이가 int로 표현 가능한 2^31-1 이하의 정수라고만 했지, 여기다 1을 더해서 풀라는 말은 안했으니까 여기에 Integer.MAX_VALUE를 넣어주면 overflow가 발생하는게 당연하다.
그렇게 고친 주요 코드는 다음과 같다.
long maxLength = Long.MIN_VALUE;
long low = 0;
long high = lengthOf[NUM_OF_CABLES - 1] + 1;
while (low <= high) {
long candidateLength = (low + high) >> 1;
long cableCnt = 0;
for (int cable = getLowerBound(lengthOf, candidateLength); cable < NUM_OF_CABLES; cable++) {
cableCnt += (lengthOf[cable] / candidateLength);
}
if (cableCnt >= REQUIRED_CABLES) {
maxLength = candidateLength;
low = candidateLength + 1;
} else {
high = candidateLength - 1;
}
}구간의 타입을 일관되게 long으로 만들어 줬으니, int 타입 두 개 더한다고 overflow가 나진 않을 것이다. 조앗서 제출!
상상도 못한 / by zero
진짜 오랜만에 만나서 잘못 본건가 싶었다. 어 그,, 왜?
다행히도 딱 한 부분에서만 나눗셈 연산이 들어가 있었다.
cableCnt += (lengthOf[cable] / candidateLength);또 여기야 또,, 그럼 candidateLength가 0이 되는 케이스가 있다는 말인데
long candidateLength = (low + high) >> 1;low + high가 0이거나 1이어야 candidateLength가 0이 될테고, high는 자연수인 랜선 길이에 1까지 더해줬으니 범인이 아니다. 그렇다면 범인은 low인데,,
long low = 0;엉? 엥? 맞지 않나? 어제도 분명 이렇게 했는데?
ㅋ,, ㅋㅋㅋㅋ 여기서 크게 깨달았다. 다음 차례 골드 난이도 Parametric Search 풀기 전에 다른 실버 좀 더 열심히 풀어봐야겠다고,,
반례는 다음과 같다.
1 3
3길이 3짜리 랜선을 잘라서 적어도 3개의 랜선을
이런 입력이 들어오면 아래와 같이 작동할 것이다.
[low, high] = [0, 3+1] = [0, 4]로 초기화- Iter 1)
mid = (0 + 4) / 2 = 2, 1개의 케이블을 얻을 수 있으므로 더 짧게 잘라야 함 - Iter 1) 따라서
[0, 4]를[0, 1]로 초기화 - Iter 2)
mid = (0 + 1) / 2 = 0, 여기서 예외 발생
,,하는 일이 생겼다. 애초에 [low, high]가 자르는 길이가 될 수 있는 해가 존재하는 집합 같은건데, 가장 작은 값을 0으로 놨으니 당연히 틀릴 수밖에,,
따라서 이 low의 초기값을 1로 바꿔주면?
정답 코드 전문
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
* 1. 길이가 서로 다른 K개의 랜선이 있다.
* 2. 이때 모두 같은 길이를 가지는 랜선을 N개 만들고자 한다.
* 3. 결정한 길이보다 짧게 남겨진 랜선은 버려진다.
* 4. 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다.
* 5. 랜선을 자를 때는 항상 정수 길이 단위로 자른다.
* 6. 만들 수 있는 가장 긴 랜선 길이를 구하자.
*/
public class Main {
static final BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static final StringBuilder out = new StringBuilder();
static StringTokenizer st;
public static void main(String[] args) throws Exception {
st = new StringTokenizer(in.readLine());
// 랜선의 개수 [1, 10,000]
final int NUM_OF_CABLES = Integer.parseInt(st.nextToken());
// 필요한 랜선의 수 [1, 1,000,000] (NUM_OF_CABLES <= REQUIRED_CABLES)
final int REQUIRED_CABLES = Integer.parseInt(st.nextToken());
// 가지고 있는 랜선의 길이들 (자연수)
long[] lengthOf = new long[NUM_OF_CABLES];
for (int cable = 0; cable < NUM_OF_CABLES; cable++) {
lengthOf[cable] = Long.parseLong(in.readLine());
}
// 이분 탐색을 위한 정렬
Arrays.sort(lengthOf);
long maxLength = Long.MIN_VALUE;
long low = 1;
long high = lengthOf[NUM_OF_CABLES - 1];
while (low <= high) {
long candidateLength = (low + high) >> 1;
long cableCnt = 0;
for (int cable = getLowerBound(lengthOf, candidateLength); cable < NUM_OF_CABLES; cable++) {
long length = lengthOf[cable];
cableCnt += (length / candidateLength);
}
if (cableCnt >= REQUIRED_CABLES) {
maxLength = candidateLength;
low = candidateLength + 1;
} else {
high = candidateLength - 1;
}
}
System.out.println(maxLength);
}
private static int getLowerBound(long[] numbers, long targetNum) {
int low = 0;
int high = numbers.length;
while (low != high) {
int mid = (low + high) >> 1;
if (numbers[mid] >= targetNum) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
}
드디어 정답,,!
마무리
오늘은 두 가지 배웠다.
- Overflow가 날지 안날지, 항상 입력의 크기 뿐만 아니라 코드 안에서 연산의 결과까지도 신경쓰자.
- 틀 '만' 생각하지 말고 한 라인 한 라인 이유를 납득하고 작성하자.
진짜 진짜 가끔 Python 생각이 나기도 하는데 오늘은 좀 더,, 그립다,, 😢
