백준 1654번 C++ 풀이

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

시간 제한	메모리 제한	문제 티어
2초	128MB	실버3

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 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개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

예제 입력

4 11
802
743
457
539

예제 출력

200

---

이 문제를 처음 봤을 때는 이분탐색으로 모르는 상태였어서 어떻게 해도 틀렸다고 나와서 포기했던 문제이다. 하지만 이분탐색을 배우고, 이 문제를 다시 봤지만, 그래도 어려웠다.

 

이 문제는 이분탐색, 그 중에서도 파라메트릭 서치를 써야 한다. 이분 탐색은 정렬된 일련의 값들중에서 주어진 하나의 값을 찾는 알고리즘이지만, 파라메트릭 서치는 주어진 범위에서 조건을 만족하는 최대(혹은 최소)값을 찾는 알고리즘이다. 얼핏 보면 다른 알고리즘 같지만, 이 두 알고리즘은 작동하는 방식이 매우 유사하다. 자세한건 여기서 확인하자(https://sarah950716.tistory.com/16).

 

파라메트릭 서치로 풀이를 하기 위해서는 다음과 같은 조건을 만족해야 한다.

• 특정 조건을 만족하는 최대 or 최솟값을 찾는 문제여야 한다.
• (특정 조건을 만족하는 최댓값을 찾는 문제에서) 최댓값 x에 대해 x보다 작은 수들은 모두 조건을 만족해야 한다.
• (특정 조건을 만족하는 최솟값을 찾는 문제에서) 최솟값 x에 대해 x보다 큰 수들은 모두 조건을 만족해야 한다.
• 답의 범위가 이산적이거나, 허용 오차 범위가 존재해야 한다. 연속적인 범위라면 한없이 가까워질 수는 있겠으나 정확한 값을 찾긴 힘들기 때문

이 문제는 주어진 랜선의 길이중 제일 긴 랜선까지 파라메트릭 서치를 통해 n개의 랜선을 만들수 있는지를 찾아야 한다.

그렇기 때문에 1 ~ (주어진 랜선길이의 최댓값)까지의 범위에서 조건을 만족하는 최댓값을 찾으면 된다.

 

또한 랜선의 길이가 2^31 - 1까지 이므로, 극단적인 상황에서 mid가 int형이라면 오버플로우가 발생할 수 있기 때문에((start + end) / 2 에서 start와 end가 제한 길이에 근접한 경우) int형보다 더 크게 잡아야 한다. 필자는 unsigned int형으로 풀었다.

 

#include <iostream>
using namespace std;
typedef unsigned int uint;

int count_lan_cable(int* arr, int arr_len, unsigned int len) {
    int count = 0;
    
    for(int i = 0; i < arr_len; i++) 
        count += arr[i]/len;
    
    return count;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int k, n;
    uint start = 1, end = 0;
    uint result;
    uint mid;

    cin >> k >> n;

    int* arr = new int[k];
    
    for (int i = 0; i < k; i++) {
        cin >> arr[i];
        end = arr[i] > end ? arr[i] : end;
    }

    while (start <= end) {
        mid = (start + end) / 2;
        if (count_lan_cable(arr, k, mid) >= n) {
            start = mid + 1;
            result = mid;
        } else 
            end = mid - 1;
    }
    cout << result;
    delete[] arr;
}

 

 

참고한 사이트

• https://sarah950716.tistory.com/16
• https://ialy1595.github.io/post/parametric-search/
• https://www.crocus.co.kr/1000