C++[baekjoon] 15810번: 풍선 공장

 

이 문제의 핵심은 단조성이다.

 

단조성이란 어떤 값이 계속 증가하거나 감소하는 성질을 의미한다.

이 문제에서 우리가 찾고자 하는 것은 M개의 풍선을 만들기 위한 최소 시간인데 그 시간을 기준으로 보면 "어떤 시간 t에서 가능했다면, 그보다 더 큰 시간에서도 가능하다" 는 규칙이 성립한다.

t 시간 안에 M개의 풍선을 만들 수 있다면,
t+1, t+2, ... 같은 더 큰 시간에서도 M개 이상을 만들 수 있다.

 

이런 특성을 보일 때, 단조성을 띈다고 한다.

 

따라서 이 문제는 답이 단조 증가하는 특성이 있으므로
이분 탐색을 적용하면 O(log T * N) 의 시간 복잡도로 해결할 수 있다.

 

1. 시간의 범위를 설정

• 최소 시간 l = 1
• 최대 시간 r = 10^12 (최악의 경우 -> 어떤 사람이 1개의 풍선을 만드는데 걸리는 시간이 1,000,000일때 혼자서 1,000,000개의 풍선을 만들어야하는 경우)

2. 중간값 mid 를 설정하여 검사

• mid 시간 동안 풍선을 M개 이상 만들 수 있는지 확인
• mid 시간 안에 가능하다면, 더 작은 시간도 가능할 수 있으므로 r = mid - 1
• 불가능하다면 시간이 부족하므로 l = mid + 1

3. 탐색 종료 후 ans 값이 최소 시간

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int N,M; scanf("%d %d", &N, &M);
    vector<int> v(N);
    for(int i=0; i<N; i++){
        scanf("%d", &v[i]);
    }
    long long l=1, r=1e12, ans;
    while(l<=r){
        long long mid=(l+r)/2, count=0;
        for(int i=0; i<N; i++){
            count+=(mid/v[i]);
        }
        if(count>=M){
            ans=mid;
            r=mid-1;
        } else{
            l=mid+1;
        }
    }
    cout<<ans;
}

 

출처: https://www.acmicpc.net/problem/15810