[백준] 1654번 : 랜선 자르기

문제

 

---

풀이

 

parametric search 문제라고 써있었다. 근데 난 이게 뭔지 모르니 검색을 해보았다.

 

www.crocus.co.kr/1000

파라매트릭 서치(Parametric Search)

이 글을 보고 완벽하게 이해했다.

 

그렇다면 이 문제에서 left와 right는 무엇일까?

랜선의 길이가 0cm일 수는 없으니까 left는 1일 것이다.

그리고 막연하게 right는 가장 짧은 랜선의 길이와 같지 않을까..?라고 생각했다. 하지만 틀렸다.

 

입력 값이

2 2

1

100

으로 들어왔다고 하자.

 

딱봐도 출력값은 50이어야 한다. 하지만 right를 가장 짧은 랜선의 길이로 잡으면 1을 출력할 것이다.

그렇기 때문에 right는 가장 긴 랜선의 길이로 해야한다.

 

대충 left=1, right=10이고 2개의 랜선이 필요하다고 하자.

mid 값은 5가 나왔고, 이런 저런 계산을 통해 5cm의 랜선은 총 3개를 구할 수 있다고 해보자.

우린 2개만 필요하니까 길이를 좀 늘려도 될 것 같다.

 

2개다! 그럼 이제 리턴하면 될까?

아니다 9cm, 10cm의 랜선도 2개가 나올 수 있다. 그러므로 좀 더 오른쪽으로 가봐야겠다.

 

몇번 더 반복문을 돈 결과이다.

이 문제는 그니까 랜선의 수가 2인 것 중에 가장 길이가 긴 upper_bound를 구하는 것이다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

int K, N;
vector<ll> wire;

ll cntWire(ll length) { //랜선이 총 몇개가 나오는지 계산
    ll cnt = 0;

    for (int i = 0; i < wire.size(); i++)
        cnt += (wire[i] / length);
    return cnt;
}

ll upperSearch(ll left, ll right) { //upper_bound를 찾는 문제와 같음.
    while (left <= right) {
        ll mid = (left + right) / 2;
        ll wires = cntWire(mid);
        if (wires < N)
            right = mid - 1;
        else if (wires >= N) //else로 처리할 수 있지만 lower랑 비교하기 위해 유지
            left = mid + 1;
    }
    return right;
}

int main() {
    ll input;

    cin >> K >> N;
    for (int i = 0; i < K; i++) {
        cin >> input;
        wire.push_back(input);
    }
    sort(wire.begin(), wire.end()); //정렬

    cout << upperSearch(1, wire[wire.size() - 1]); //제일 큰걸로!
}

전체 소스코드다.

 

ll upperSearch(ll left, ll right) { //upper_bound를 찾는 문제와 같음.
    while (left <= right) {
        ll mid = (left + right) / 2;
        ll wires = cntWire(mid);
        if (wires < N)
            right = mid - 1;
        else if (wires >= N) //else로 처리할 수 있지만 lower랑 비교하기 위해 유지
            left = mid + 1;
    }
    return right;
}

upper_bound를 구하는 함수이다.

 

myunji.tistory.com/263

[백준] 10816번 : 숫자 카드 2

여기 있는 코드와 거의 유사하다.

 

다만, mid 길이의 랜선이 몇개가 나오는지 계산하는 과정이 필요하다.

 

ll cntWire(ll length) { //랜선이 총 몇개가 나오는지 계산
    ll cnt = 0;

    for (int i = 0; i < wire.size(); i++)
        cnt += (wire[i] / length);
    return cnt;
}

그걸 하는 함수다. 별로 어렵진 않으니 굳이 설명하진 않겠다.