Gidhub BE Developer

[BOJ] 1654. 랜선 자르기

2018-09-26
goodGid
Algorithm

Problem

Problem URL : 랜선 자르기

[1] Answer Code (18. 09. 26)

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

ll n,k;
ll arr[10001];
ll ans;


void bst(ll l, ll r){
    if( l > r)
        return ;
    
    ll mid = (l+r) >> 1;
    int cnt = 0;
    
    for(int i=0; i<n; i++){
        cnt += arr[i] / mid;
    }
    
    if( cnt == k ){
        ans = ans < mid ? mid : ans;
        bst(mid+1, r);
    }
    else if( cnt > k ){
        ans = ans < mid ? mid : ans; // [1]
        bst(mid+1, r);
    }
    else
        bst(l, mid-1);
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i=0; i<n; i++){
        cin >> arr[i] ;
    }
    sort(arr, arr+n);
    bst(1,arr[n-1]); // [2]
    cout << ans << endl;
    return 0;
}

Review

  • [1] 부분이 왜 있어야하는지 모르겠다. 그런데 없으면 틀린다.

  • 좀 찾아보니까 이런 댓글이 있었다.
    만약 만들 수 있는 랜선의 개수가 입력에서 주어진 필요한 랜선의 개수 보다 커도 결론적으로 필요한 랜선만큼을 만들 수 있기 때문인 것 같네여

  • 내가 이해력이 부족한 것인가 문제가 좀 이상한 것인가…

  • 아무튼 이 문제의 핵심은 파라메트릭 서치 알고리즘을 사용하는 것이다.

  • 파라메트릭 서치(Parametric Search)에 대해 알아보도록 하자.

[2] Answer Code (18. 09. 26)

#include<iostream>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
ll n,m;
ll ans;
ll arr[10001];

void b_s(ll l, ll r){
    if( l > r ) {
        ans = r;
        return ;
    }
    ll cnt = 0;
    ll mid = (l+r) >> 1;
    for(int i=0; i<n; i++){
            cnt += arr[i] / mid;
    }
    
    if( cnt < m ){
        b_s(l, mid - 1);
    }
    else {
        b_s( mid + 1 , r);
    }
}

int main(){
    cin >> n >> m;
    for (int i=0; i<n; i++)
        scanf("%lld",arr+i);

    sort(arr, arr+n);
    b_s(1,arr[n-1]);
    cout << ans << endl;
    return 0;
}

Review

  • ans를 갱신하는 시기를 left > right 보다 클 경우에 해주면 된다.

  • 탐색을 계속하다 끝나는 시점은 무조건 left과 right이 겹치는 부분이다.

  • 즉 그 때가 최적의 답이다.

  • 아무튼 이 문제의 핵심은 파라메트릭 서치 알고리즘을 사용하는 것이다.

  • 파라메트릭 서치(Parametric Search)에 대해 알아보도록 하자.

Recommend

Index