백준 1654 - 랜선 자르기
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net
개요
parametric search는 이진 탐색의 원리를 이용해서 최적의 해를 구하는 방법이다.
최적화 문제를 결정 문제로 바꾸어 푸는 것이다.
정렬된 어떠한 리스트에서 탐색 기준을 결정해 놓고 특정 위치에서 기준에 만족하지 않는 다면 그 아래있는 위치들도 모두 기준에 통과하지 못할 것이라는 확신으로 문제를 해결하는 것이다.
O(logN + a)의 시간 복잡도를 가진 parametric search 알고리즘은 이진 탐색과 마찬가지로 정렬된 연속적인 값들에 대해서 탐색의 범위를 1/2 씩 줄여나가며 최적의 답을 찾는 알고리즘이. 알고리즘의 개념은 아래 링크를 참고하고 여기서는 문제 풀이를 예시로 설명해보겠다.
파라매트릭 서치(Parametric Search)
목차 1. 파라매트릭 서치(Parametric Search)란? 2. 예시를 통한 파라매트릭 서치(Parametric Search) 3. 시간 복잡도 4. 정리 5. 관련 문제 1. 파라매트릭 서치(Parametric Search)란? Parametric Search에 대해 알아보자.
www.crocus.co.kr
문제 해석
탐색 범위 설정
|
1
2
3
|
int start;
int end;
int mid = (start + end) / 2
|
cs |
이분 탐색을 학습했다면 이미 익숙한 변수 설정일 것이다. Parametric search에서도 동일하게 탐색의 범위를 설정한다.
- 오영식이 만들고자 하는 랜선의 개수는 1이상 1,000,000이하의 정수
- 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정
우선 초기 end의 값은 위 조건에 의해 오영식이 가지고 있는 랜선 중 제일 긴 랜선 길이가 된다.
start 값은? 랜선이라는 물체적 특성 상 음수의 길이를 가질 수 없다. 또 만들고자 하는 랜선의 개수가 1개 이상이니 0 이 될수도 없다. 따라서 초기 start 값은 1이 된다.
탐색
앞에서 설정한 탐색 범위에 의해서, 예시의 탐색 범위는 start = 1, end = 802가 된다. 앞으로 탐색은 최소와 최대의 중앙값을 가지고 비교를 시작한다. 최소와 최대는 중앙값의 비교 결과에 따라 변경된다.
현재 중앙 값은 401이다. K개의 랜선에서 401cm의 랜선을 만들어보면 다음과 같다.
802 - 2개
743 - 1개
457 - 1개
539 - 1개
401cm의 길이인 랜선은 5개만 생성할 수 있다. 오영식은 11개 이상의 랜선을 만들고 싶어야 하기 때문에 401cm는 적절하지 않다. 이제 탐색의 범위를 재설정해야 한다. 401cm로 설정했을 때 모자랐기 때문에 401cm 이상으로 설정하면 절대로 11개를 생성할 수 없다. 따라서 end의 값을 401 - 1 즉, 400으로 변경한다.
이제 탐색의 범위는 start = 1, end = 400이다. 그리고 mid는 200이 된다.. 200cm로 랜선을 만들어보자.
802 - 4개
743 - 3개
457 - 2개
539 - 2개
200cm의 길이인 랜선은 11개를 생성할 수 있다. 오영식이 원하는 랜선의 갯수와 동일하다. 하지만 여기서 탐색을 종료하면 안된다. 문제에서는 N개 이상의 랜선을 생성하는 경우도 적합하다 하였고, 최대 랜선의 길이를 구하는 것이 목표였기 때문이다.
랜선을 11개 이상 생성하는 경우는 200cm뿐만이 아닐 수 있으며, 최대 랜선의 길이를 구하는 것이기에 200cm 아래로는 탐색할 필요가 없다. 따라서 start의 값을 200 + 1 즉, 201로 변경하여 탐색을 다시 한다.
결과적으로 이진 탐색의 종료 조건과 같이 start가 end보다 커지는 순간 parametric search은 종료된다.
전체 코드
|
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
45
46
47
48
|
public class _1654_랜선자르기 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
long answer = 0;
String[] NM = br.readLine().split(" ");
int N = Integer.parseInt(NM[0]);
int M = Integer.parseInt(NM[1]);
long left = 1;
long right = 0;
int[] lans = new int[N];
for (int i = 0; i < N; i++) {
lans[i] = Integer.parseInt(br.readLine());
right = Math.max(lans[i], right);
}
System.out.println(left + ", " + right);
while (left <= right) {
long mid = left + (right - left) / 2;
int count = 0;
for (int lan : lans) {
count += (lan / mid);
}
if (count >= M) {
answer = Math.max(mid, answer);
left = mid + 1;
} else {
right = mid - 1;
}
}
bw.write(answer + "\n");
bw.flush();
br.close();
bw.close();
}
}
|
cs |
결국 해당 문제도 이분 탐색의 연장선일 뿐이다.
단지 domain을 문제에 맞게 적절하게 설정하여 푸는 문제 같았다.
다른 문제 예시
정수형 배열 nums 와 정수 m 이 주어졌다.
nums 에는 양의 정수 값들이 들어 있고, m 은 배열을 부분 배열로 분리할 수 있는 수이다.
nums 배열을 m 개의 부분 배열로 분리할 때,
각 부분 배열의 합 중 가장 큰 값이 최소가 되도록 분리했을 때의 합을 출력하세요.
// 입출력 예시
// nums: 7, 2, 5, 10, 8
// m: 2
// 출력: 18
// nums: 1, 2, 3, 4, 5
// m: 2
// 출력: 9
해당 문제도 결국 문제로 주어진 nums가 아니라 domain을 각 부분 배열의 합으로 생각해보자.
이때 부분 배열의 최소 단위인 1개 일 때의 최대값은 10, 부분 배열 최소 단위인 5개일 때의 최대값은 32이다.
이렇게 domain을 변경하여 문제 풀이를 위한 범위를 재 설정하는게 parametric search 문제의 접근 방법인 것 같다.