🧩 BE
home

1654_랜선 자르기

담당자
완료 여부
Solved
요약
날짜
2025/04/03
태그
이진탐색
난이도
S2
출처
백준
이분 탐색 문제라 좀 간단하게 풀릴 줄 알았는데, 고려해야하는 조건이 꽤 많아서 힘들게 풀었다.
먼저 일반적인 이분 탐색 문제와는 다르게 중간값을 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
복사