[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보다 작거나 같은 자연수이다.

4 11
802
743
457
539

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

200

---

Parametric search 기법을 사용하는 문제를 풀어봤다. 적당한 후보를 결정하고 그 후보가 실제로 문제의 답이 될 수 있는지 검증하는 과정을 통해서 문제를 해결한다. 이 기법을 적용하기 위해서는 조건이 있다. 우선, 문제의 답이 될 수 있는 후보들이 연속적이어야 한다. 또한, 답이 겹치는 부분이 있다고 해야하나? 이 예시로 주어진 입력을 예로 들면, 11개의 랜선을 만들 수 있는 최대 길이는 200이다. 이때 랜선의 길이가 199인 경우도 11개의 랜선을 만들 수 있다. 문제의 답을 찾는 과정에서 만약 길이가 300인 랜선으로 11개를 만들 수 없다면 300이상은 볼 것도 없이 불가능하다. 이런 조건 하에서 적용할 수 있는 기법이다.

 

후보를 찾기 위해서는 이분 탐색을 사용했다. 정답이 될 수 있는 구간의 중간 값을 검증하고 가능하다면 구간을 오른쪽으로 이동하고 불가능하다면 왼쪽으로 이동하면 검증 과정을 제외하고 O(logn)에 답을 찾을 수 있다. 이 문제는 주어진 제약 조건 하에서 최대를 찾는 문제였지만, 어디서 얼핏 최소가 되는 최대를 구하는 문제도 보통 이분 탐색을 사용하면 풀 수 있다고 들었던 것 같다.

 

입력되는 숫자의 범위가 int형의 끝까지 가버리기 때문에 사용하는 변수들은 long long으로 했다. 초기 구간의 오른쪽 끝을 INT_MAX로 사용했더니 55%쯤에서 틀렸는데 LLONG_MAX로 바꿔주니 해결됐다.

 

 

후기)

Parametric search을 사용할 때 후보 결정 방법으로 이분 탐색 말고 다른 방법을 사용하는 경우는 어떤 상황일까하고 고민해봤다. 평범한 상황이라면 순차적으로 고르는 방법은 이분 탐색에 비해 장점이 전혀 없는 것 같다. 알고리즘의 비용을 줄이고 싶으면 후보 결정보다는 후보가 실제로 답이 될 수 있는지 검증하는 알고리즘을 어떻게 야무지게 짤지 고민하는게 더 좋지 않을까 하는 생각도 들었다. 뭐 이것도 경우에 따라 다르겠지.