백준, BOJ, 1654번 C++ [CPP]

아주아주 착각에 빠지기 쉬운 문제다.

물론 시간이 많지만 입력이 드럽게 많기 때문에 생략하고

풀어보자

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

 

---

 

#틀린 풀이 일부

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> K >> N;

    for (int i = 0; i < K; i++) {
        long long a;
        cin >> a;
        arr[i] = a;
    }
    sort(arr, arr + K); // 오름차순
    standard = arr[K-1]; // 최댓값


    while (1) {
        for (int i = K-1; i > 0; i--) {
            sum += (arr[i] / standard);
        }
        if (sum >= N) {
            cout << standard;
            break;
        }
        else {
            sum = 0;
            standard--;
        }
    }
}
*/

 

어떻게 생각했냐면

어차피 가장 길게 자르는 랜선의 길이 또한

내가 갖고 있는 제일 작은 랜선의길이보다 작거나 같지 않을까?

 

근데 간과한 조건이 있다.

꼭 내가 가지고 있는 모든 랜선을 이용할 필요는 없었다.

즉, 가장 짧은 것을 사용하지 않아도 된다는 말이다.

 

그냥 내가 가지고 있는 것들로 어떻게 X개 이상 만들까?? 또한 가장 길게 만들까??

즉,

극단적인 예로

4개를 가지고 있고 5개를 만들고 싶다.

아래 4개를 가진다.

1000

1

2

3

1로 나누면 분명 1006개가 나와서 좋다. 하지만 가장 길까?

2로 나누면 502개

3으로 나누면 334개

4로 나누면 250개 ??? 어 내가 가지고 있는 최소 랜선 길이보다 길어도 5개 이상 만들어지네..?

 

즉, 최솟값이 문제가 아니라 최댓값이 문제였다.

 

최댓값에서 나누어가면서 만들어야 했다.

하지만 선형 탐색하기엔 입력이 너무 많아서 이진탐색을 이용해야 했다.

 

#맞는 풀이

#include<iostream>
#include<algorithm>

using namespace std;

int N, K;

long long arr[10001];
long long ans = 1;

long long M = 0;

bool func(long long n){
    long long cnt = 0;
    for(int i = 0; i<N; i++){
        cnt += arr[i]/n;
    }
    return(cnt >= K);
}

//이분탐색 사용해야함
int main(){
    cin >> N >> K;
    for(int i = 0; i<N; i++){
        int a;
        cin >> a;
        arr[i] = a;
        if(M<a){
            M = a;
        }
    }
    
    //값의 범위 2^31-1 이하의 자연수
    long long low = 1;
    long long high = M;

    
    while(low <= high){
        long long mid = (low+high)/2; // 해당숫자
        
        //해당 숫자가 K 이상의 랜선을 만들면 더 커질 수 있는 랜선이 있나 조사해야함.
        //우선 해당값을 저장하고 오른쪽 다시 탐색.
        if(func(mid)){
            if(ans<mid){
                ans = mid;
            }
            low = mid+1;
        }else{ // 못만들면 숫자를 작은 것을 선택해야함.
            high = mid-1;
        }
    }
    
    cout << ans ;
    
}