(C++) 백준 1654번 - 랜선 자르기

문제 링크 : https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

풀이

매개 변수 탐색을 사용해 풀이하였다.

매개 변수 탐색은 다음의 두 조건을 만족할 경우에 사용할 수 있다.

1. 최적화 문제를 결정 문제로 변경할 수 있는지?
2. 위의 결정 문제로 얻어진 함수가 감소 혹은 증가함수인지?

여기서는 N개를 만들 수 있는 최대의 랜선을 구하는 최적화 문제를 랜선의 길이가 X일 때 랜선의 개수가 N개 이상인가 아닌지 구하는 결정 문제로 변경할 수 있다.

또한 랜선의 길이가 길어짐에 따라, 만들 수 있는 랜선의 길이는 줄어드는 감소 함수이기에 매개 변수 탐색을 사용할 수 있는 것이다. 

#include <iostream>

typedef long long ll;
using namespace std;

int a[10005];
int k, n;

bool solve(ll mid){ // mid의 길이로 만들 수 있는 랜선의 수가 n보다 클 수 있는지
    ll cur = 0; // 만들 수 있는 랜선의 수
    for(int i = 0; i < k; i++) cur += a[i] / mid;
    return cur>=n;
}

int main() {
    ios::sync_with_stdio(0);  
    cin.tie(0);
    cout.tie(0);

    cin >> k >> n;
    for(int i = 0; i < k; i++) cin >> a[i];
    ll st = 1;
    ll ed = 0x7fffffff;
    while(st < ed){ // 이진 탐색
        ll mid = (st+ed+1)/2;
        if(solve(mid)) st = mid;
        else ed = mid-1;
    }
    cout << st;
}