랜선 자르기(BOJ : 1654)
백준 1654번 : 랜선 자르기
본문
제한
문제
집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.
이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.
출력
첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.
예제 입력 1
4 11
802
743
457
539
예제 출력 1
200
풀이
자르는 랜선의 길이(x)를 구해야 한다.
x 길이로 주어진 랜선들을 잘랐을 때, 랜선의 개수가 n개 이상이어야 하고, 잘린 후의 랜선 개수가 n개 이상을 만족하는 x의 최대값을 구해야 한다.
우리는 이진 탐색을 통해 조건을 만족하는 x 값을 찾을 수 있다.
이진 탐색은 정렬된 리스트에서 원하는 값을 빠르게 찾는 알고리즘이다.
리스트의 탐색 시작점과 끝점을 통해 탐색 범위를 설정하고, 반복을 통해 탐색 범위를 절반씩 좁혀가며 원하는 값이 위치한 리스트의 인덱스를 반환한다.
우리는 랜선을 자를 수 있는 길이를 리스트의 인덱스로, 랜선을 해당 길이로 잘랐을 때 얻을 수 있는 랜선의 개수를 리스트의 값으로 생각하여 문제를 풀 수 있다.
예를 들어 802, 743, 457, 539 길이의 랜선이 주어졌을 때, 설정할 수 있는 x의 길이는 0부터 입력받은 랜선의 최댓값(802)이다.
이를 리스트의 인덱스처럼 사용하고 해당 인덱스로 랜선들을 잘랐을 때 얻을 수 있는 랜선의 개수를 해당 인덱스에 위치한 리스트 값으로 사용하면 n을 만족하는 x를 얻을 수 있다.
하지만 그렇다고 조건을 만족하는 x를 바로 찾을 수 없다.
예제를 보면 802, 743, 457, 539 길이의 랜선이 주어지고 11개 이상의 랜선을 얻어야 한다.
이 때, x 값을 200으로 설정하면 802 랜선은 200 랜선 4개, 743 랜선은 200 랜선 3개, 457 랜선은 200 랜선 2개, 539 랜선은 200 랜선 2개를 얻어 총 11개(n)를 만족한다.
하지만 x 값을 195로 설정하면 동일하게 11개를 얻을 수 있지만, x 값이 최대가 아니다.
x값을 201로 설정하면 총 10개의 랜선을 얻을 수 있어 잘린 총 개수가 n개 이상이어야 한다는 조건을 만족하지 않는다.
위처럼 랜선을 잘랐을 때 얻을 수 있는 랜선 개수(count)가 n개 이상인 x는 여러 값일 수 있다.
우리는 이 범위 중에서 x의 최댓값을 구해야 한다.
이진 탐색은 크게 두 가지 방법이 있다.
Upper Bound와 Lower Bound이다.
Upper Bound로 이진 탐색을 수행하면, 찾고자 하는 특정 값을 초과하는 첫 위치를 반환한다.
Lower Bound로 이진 탐색을 수행하면, 찾고자 하는 특정 값 이상인 첫 위치를 반환한다.
리스트에서 중복 값이 있을 때, 해당 값이 등장한 처음 위치를 찾고자 한다면 Lower Bound 방법을 사용할 수 있다.
반대로 해당 값이 등장한 마지막 위치를 찾고자 한다면 Upper Bound 방법을 사용하여 해당 값을 초과하는 첫 위치를 반환받게 되는데, 이 위치의 이전 위치는 해당 값이 등장한 마지막 위치가 된다.
따라서 우리는 Upper Bound 방법을 통해 이 문제를 해결할 수 있다.
Upper Bound는 다음과 같이 구현할 수 있다.
while (min < max) {
long mid = (min + max) / 2;
int count = cut(mid);
if (count < n) {
max = mid;
} else {
min = mid + 1;
}
}
찾아야 하는 값(n)이 현재 범위의 중간 값(count)보다 크다면 현재 범위의 최대 위치(max)를 중간 위치(mid)로 설정한다.
그렇지 않다면 현재 범위의 최소 위치(min)를 중간 위치(mid) + 1로 설정한다.
이렇게 되면 count >= n 일 때 마다 탐색 범위의 시작은 현재 위치(mid)의 한 칸 오른쪽으로 설정된다.
반복문 while (min < max)를 만족하지 않게되면 min은 count >= n을 만족하는 인덱스 mid보다 1 큰 값이다.
따라서 min - 1이 우리가 원하는 count >= n을 만족하는 x의 최대값이 된다.
위 내용을 토대로 작성한 코드는 다음과 같다.
public class BOJ1654 {
private static int k;
private static int n;
private static int[] lines;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
k = Integer.parseInt(st.nextToken()); // 가지고 있는 랜선 개수
lines = new int[k];
n = Integer.parseInt(st.nextToken()); // 필요한 랜선 개수
long max = 0;
for (int i = 0; i < k; i++) {
int a = Integer.parseInt(br.readLine());
lines[i] = a;
if (max < lines[i]) {
max = lines[i];
}
}
max++;
long min = 0;
while (min < max) {
long mid = (min + max) / 2;
int count = cut(mid);
if (count < n) {
max = mid;
} else {
min = mid + 1;
}
}
System.out.println(min - 1);
}
private static int cut(long length) {
int count = 0;
for (int i = 0; i < k; i++) {
count += (lines[i] / length);
}
return count;
}
}
while 반복문 전에 max++을 수행한 이유는 while문에서 mid 값이 0으로 설정되지 않도록 하기 위함이다.
만약 mid가 0으로 설정된다면 cut() 메서드에서 lines[i]를 0으로 나눠버리게 된다.
만약 1, 1 길이인 랜선 두개가 입력으로 주어진다면, max 초기값은 1, min 초기값은 0이 되고,
이진 탐색을 진행하는 while문으로 진입하게 된다면 mid 초기값이 (1 + 0) / 2로 0이 되어버린다.
이를 방지하기 위해 max 초기값에 1을 더해 준 것이다.