문제 링크
문제
이분탐색 분류의 문제임을 알고 있어 쉽게 접근법을 생각할 수 있었다.
풀이
최대 길이 자체를 이분탐색을 통해 탐색하는 것이 핵심이다. 일정 길이를 가정하고 해당 길이로 랜선이 몇개 나오는 지 확인한다. 결과에 따라서 탐색범위를 조정하고 좁혀나간다.
길이 len을 가정하고 cables을 확인하며 해당 길이로 잘랐을 때 나오는 랜선의 개수 count를 확인한다.
count>=N인 경우 ->len을 더 큰 값으로 탐색한다.count<N인 경우 -> 더 많은 랜선이 필요하므로len을 더 짧은 값으로 탐색한다.
전형적인 이분탐색의 풀이 방법이다.
주의할 점
문제는 채점 도중 시간초과가 났다는 것이다. Java로 푸는 중이었기 때문에 혹시.. 자바여서 그런가..? 라는 생각에 cpp로 같은 코드를 제출했음에도 시간초과가 났다.(채점 기준이 다를 것임을 앎에도 불구하고 자바 속도에 대한 불신으로 가득한 상태이다.)
코드를 보면 시간초과를 해결하기 위해 꽤 애를 썼다는 것을 느낄 수 있다. cables를 정렬해서 자르지 않아도 원하는 길이가 되지 않는 순간 반복문을 종료하도록 했다. 또 이미 필요 케이블을 충족한 경우에도 cables의 탐색을 종료한다. 마지막으로 초기 right값을 가장 긴 케이블의 길이로 설정해줌으로 써 나의 간절함을 코드에 담았다.(이건 솔직히 의미 없었을 것 같다. O(logX)이기 때문에..)
결국 항복하고 질문하기를 봤는데, 자료형때문이었다.
cable의 최대길이가 int범위이기 때문에 int형을 사용하면 충분할 것이라고 생각했다. 하지만 이렇게 했을 때 문제는 가능한 케이블을 세는 과정에서 int형을 초과할 수 있다. 예를 들어 N=1인데 cable의 길이가 2^31이면 한 번에 count가 2^31씩 증가하게 된다. 즉 이렇게 N이 작고 cable의 길이가 매우 큰 경우 범위 초과의 가능성이 존재한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main{
private static int K,N;
private 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());
List<Integer> cables = new ArrayList<>();
long left = 1, right = 1, mid, count, tmp;
K = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
for(int i=0; i<K; i++){
int len = Integer.parseInt(br.readLine());
right = Long.max(right, len);
cables.add(len);
}
Collections.sort(cables, Collections.reverseOrder());
while(left<=right){
mid = left + (right-left)/2;
count = 0;
for(int i=0; i<cables.size(); i++){
tmp = cables.get(i)/mid;
if(tmp==0) break;
else count+=tmp;
if(count>=N) break;
}
if(count>=N){
answer = Long.max(answer, mid);
left = mid+1;
}
else{
right = mid-1;
}
}
System.out.println(answer);
}
}