1654번: 랜선 자르기 - Baekjoon Online Judge
https://www.acmicpc.net/problem/1654
랜선 자르기 문제는 이분 탐색을 이용하여 범위 내에서 원하는 개수의 랜선을 만들되 그 길이는 최대값이 되도록 하는 문제이다. 원하는 값을 찾기에는 너무 많은 값을 하나씩 대입해야 하기 때문에 이분 탐색을 이용하여 가능한 후보군을 줄임으로써 시간내에 원하는 값을 찾을 수 있다.
이분 탐색 문제를 푼다고 했을 때 구현에서 차이가 나는 부분은 어떤 기준으로 중앙값을 옮겨줄 것인가이다. 이 문제의 경우 주어진 랜선을 적절하게 잘라서 원하는 개수를 맞춰주는 것이기 때문에 랜선의 길이가 중앙값 이동의 기준이 된다. 처음 중앙값은 0에서 int의 max값 사이에 있다는 것을 가정하고 그 중간값으로 계산을 시작했다. 중앙값을 구한 후, 주어진 랜선들을 이용하여 중앙값 길이의 랜선을 몇 개 만들수 있는지 카운팅을 해준다. 개수가 너무 많은 경우라면 중앙값을 더 큰쪽으로 이동시켜줘서 개수를 줄이고 길이는 늘려주는 쪽으로 탐색해주고, 만일 개수가 부족하다면 중앙값을 더 작은쪽으로 이동시켜서 개수를 늘리고 길이는 줄이는 방향으로 탐색을 이어나간다. 또한 우리는 개수만 만족한다고 해서 답을 찾았다고 할 수 없고 개수를 만족하는 랜선 길이 중에서도 최대값을 찾아야 하기 때문에 개수를 만족하는 중앙값 중에서도 제일 큰 값을 답으로 저장해서 출력해야한다.
실제 문제에서는 어떻게 구현했는지 소스를 통해 살펴보자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static int N; private static int K; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; st = new StringTokenizer(br.readLine().trim()); K = Integer.parseInt(st.nextToken()); N = Integer.parseInt(st.nextToken()); long[] L = new long[K]; for (int i = 0; i < K; i++) { L[i] = Long.parseLong(br.readLine().trim()); } long l = 0; long r = Integer.MAX_VALUE; long max = 0; long m = 0; int cnt = 0; while (l <= r) { m = (l + r) / 2; cnt = 0; for (int i = 0; i < K; i++) { cnt += (L[i] / m); } if (cnt >= N) { l = m + 1; if (max < m) max = m; } else { r = m - 1; } } System.out.println(max); } } | cs |
'Algorithm > Algorithm Study' 카테고리의 다른 글
LIS (Longest increasing subsequence) nlogn 해법 (0) | 2017.12.31 |
---|---|
1102번: 발전소 - Baekjoon Online Judge (0) | 2017.12.20 |
2162번: 선분 그룹 - Baekjoon Online Judge (0) | 2017.11.28 |
CCW(CounterClockWise) 알고리즘 (0) | 2017.11.21 |
사이클 찾기: DFS (0) | 2017.11.21 |