• 문제 링크

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

  • 사용 언어

    C++

  • 소스

    #include <iostream>
using namespace std;
  
int N, K;
int A[10000];
  
bool possible(int q){
	int count = 0;
	for(int i = 0; i < N; i++)count += A[i]/q;
	return count >= K;
}
  
int main()
{
	cin >> N >> K;
	for(int i = 0; i < N; i++) cin >> A[i];
	long long p = 1;
	long long q = ~(1 << 31);
	long long r = q;
  	
	while(p != q || q != r){
		if(possible(q)) {
			p = q;	
			q = (p+r)/2 + 1;
		}
		else {
			r = q-1;	
			q = (p+r)/2;
		}
	}
	cout << q;
}

  • 논리

    임의의 용량 w로 K명 에게 나눠줄 수 있는지 여부를 판단해보자.

    각 주전자의 용량을 Ai라 하자.

    w씩 나눠줬을 때, 최대 나눠줄 수 있는 인원수 y를 구하는 방법은 다음과 같다.

    \[y=\lfloor \frac{A_{_{1}}}{w}\rfloor+\lfloor \frac{A_{_{2}}}{w}\rfloor+...+\lfloor \frac{A_{_{N}}}{w}\rfloor\]

    이 때 y >= K 이면 K명에게 나눠줄 수 있음을 알 수 있다.

    이 판정 알고리즘의 시간복잡도는 O(N)이다.

    이제 이 알고리즘을 사용하여 용량 w로 나눠줄 수 있는지 판정하는 함수를

    possible(w)로 정의하겠다.


    자, 그럼 간단히 생각해보면 w를 1부터 시작하여 점차 증가시켜 나가며

    possible(w)을 검사하면 되지 않을까?

    그러다가 possible(w)값이 false가 되기 직전이 바로 w의 최대값이 될 것이다.

    그러면 이 알고리즘의 시간복잡도는 얼마나 될까?

    w의 범위부터 알아보자. 아래와 같이 w의 범위를 구할 수 있다.

    \[w*K\le\sum_{i=1}^N A_{i}\le N*M_{0}\qquad(M_{0}=max(\{A_{i}\}))\\ \Rightarrow w\le\frac{N}{K}*M_{0}\\ \Rightarrow w<M_{0}\qquad(\because N<K)\]

    M0=231-1 이므로 굉장히 큰 상수 이다.

    시간복잡도는 O(N*M0)이며 시간초과 에러를 만나게 된다.


    이유는 간단하다. M0가 너무 크기 때문이다.

    선형탐색 알고리즘은 간단하지만 이 지나치게 커다란 M0에 대해서는 적절치 못했다.

    그렇기 때문에 이진탐색을 통해 시간을 극적으로 단축시킬 수 있으며

    시간복잡도는 O(N*logM0)를 얻을 수 있다.

  • 컴퓨팅적 문제

    p, q, r의 변수타입을 int가 아닌 long long으로 설정한 이유를 알겠는가.

    int타입으로 설정할 경우 만약 p+r > 231이라면

    오버플로우로 인한 계산 문제가 생기기 때문이다.