[Baekjoon] 1654: 랜선 자르기
글 작성자: SeoArc
문제

다양한 길이를 가진 n개의 랜선을 가지고 일정한 길이를 가진 k개의 랜선을 만들 때 만들 수 있는 최대 길이를 구하는 문제이다.
풀이
내 풀이
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Q1654 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] nk = br.readLine().split(" "); int n = Integer.parseInt(nk[0]); int k = Integer.parseInt(nk[1]); long[] lines = new long[n]; long max = 0; for (int i = 0; i < n; i++) { lines[i] = Long.parseLong(br.readLine()); max = Long.max(max, lines[i]); } // 이분 탐색 // 랜선 개수는 중복으로 나올 수 있기 때문에 UpperBound로 접근 후 -1 long left = 0; long right = max + 1; while (left < right) { long mid = (left + right) / 2; long count = 0; // 자른 랜선 개수 for (long line : lines) { count += line / mid; } // 개수가 k보다 작으면 랜선을 길게 자른 것이므로 right 값 변경 if (count < k) { right = mid; continue; } // 아니면 left 값 변경 left = mid + 1; } System.out.println(right - 1); } }
선형 탐색으로는 시간초과가 나기 때문에 이분 탐색으로 접근했다.
처음에 UpperBound / LowerBound 개념을 몰라서 헤메다가 결국 공부하고 다시 문제를 풀었다.
간단하게 기본 예제를 예를 들어 설명하면,
4 11 802 743 457 539
이 값에서 이분 탐색을 한다 하면, 1부터 803 사이의 값을 탐색한다.
즉 다음과 같이 803개의 배열에서 각 인덱스의 값은 랜선의 개수라고 생각하면 편리하다.
여기서 왜 802가 아닌 803을 right값으로 잡을까?
이유는, UpperBound이기 때문이다. UpperBound는 항상 원하는 값의 초과값을 가져다준다.
여기서 802를 right로 잡게될 경우, n과 k값이 1일 때 결과는 802여야 한다. 하지만 right는 절대 803이 될 수 없기 때문에 802 - 1인 801이 결과로 나오게 된다. 때문에 right를 나올 수 있는 최대 길이보다 +1 된 상태로 만들어 주어야 한다.

여기서 UpperBound로 값을 구하면 k+1의 첫번째 값, 즉 201을 구할 수 있다.
여기서 k의 최대길이 값은 구한 값에서 -1 이기 때문에 결괏값에 -1 을 하면 정답을 구할 수 있다.
회고
이분 탐색의 경곗값에 대한 개념과 right값 설정에서 많이 막힌 것 같다. 실버 문제라고 해서 만만하게 봤었지만 푸는데 좀 힘들었던 것 같다. 좀 더 기본을 단단히 다져야겠다.
'Algorithm > PS' 카테고리의 다른 글
[Baekjoon] 6064: 카잉 달력 (0) | 2023.03.18 |
---|---|
[Baekjoon] 17626: Four Squares (0) | 2023.03.17 |
[Baekjoon] 1167: 트리의 지름 (0) | 2023.03.08 |
[Baekjoon] 7662: 이중 우선순위 큐 (0) | 2023.03.08 |
[Baekjoon] 2533: 사회망 서비스(SNS) (0) | 2023.03.02 |
댓글
이 글 공유하기
다른 글
-
[Baekjoon] 6064: 카잉 달력
[Baekjoon] 6064: 카잉 달력
2023.03.18 -
[Baekjoon] 17626: Four Squares
[Baekjoon] 17626: Four Squares
2023.03.17 -
[Baekjoon] 1167: 트리의 지름
[Baekjoon] 1167: 트리의 지름
2023.03.08 -
[Baekjoon] 7662: 이중 우선순위 큐
[Baekjoon] 7662: 이중 우선순위 큐
2023.03.08
댓글을 사용할 수 없습니다.