문제

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

풀이

큰 데이터 범위와 if 조건문 처리 때문에 오답을 굉장히 많이 받았던 문제이다. 구글링 해서 나오는 코드들 중에 오답 처리되는 코드들이 많다. 주의해야 한다.

https://learn.microsoft.com/ko-kr/cpp/cpp/data-type-ranges?view=msvc-170

최악의 경우, 10^9명의 사람들이 모두 시간이 10^9초 걸리는 심사대에서 심사를 받을 수도 있다. 따라서, 최대 시간은 10^18이므로 long long 형으로 선언해줘야 한다.

cf) long long 형은 8 바이트여서 최대 크기가 2^63 - 1 (9,223,372,036,854,775,807)이므로, 10^18보다 약 8배 이상 크다.

파라메트릭 서치

최적화 문제를 결정 문제로 바꾸어 이분 탐색으로 해결하는 파라메트릭 서치로 이 문제를 풀 수 있다.

이 문제를 있는 그대로 보면 최적화 문제다. 적어도 M명을 모두 검사하는 데 걸리는 최소 심사 시간을 구해야 한다. 그런데 최적화 문제를 풀기가 어렵다! 그래서 더 쉬운 결정 문제로 바꾸어서 풀어보자.

즉, 심사 시간이 x일 때 검사할 수 있는 인원 수가 M명 이상인가? (답은 yes or no)

이 결정 문제를 만족시키는 x의 최솟값을 구하는 게 목표다.

이렇게 이분 탐색으로 x의 범위를 좁혀 나가며 최솟값을 구해보자.

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

const int MAX = 100001; 
ll times[MAX]; 
ll n, m; 

// 총 심사 시간이 x일 때, 주어진 심사대에서 
// 심사 가능한 총 인원 수가 M명 이상인가? 
bool decision(ll x){ 
	ll sum = 0; 

	// 각 심사대에서 심사 가능한 인원 수의 합을 구한다. 
	for(int i = 0; i < n; i++){
		sum += x / times[i];
		if(sum > m) break; // 이걸 안 해주면 오답 처리된다. 
	}

	return sum >= m; 
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m; 

	for(int i = 0; i < n; i++){
		cin >> times[i]; 
	}

	sort(times, times + n);
	ll left = 1;
	
	// m명이 모두 가장 오래 걸리는 심사대에서 심사 받는 경우 
	ll right = times[n - 1] * m;
	ll ans = right; 

	while(left <= right){
		ll mid = (left + right) / 2;

		if(decision(mid)) {
			ans = min(ans, mid); 

			// true 구간에서 최솟값 구하기 위해 
			right = mid - 1;
		}
		// true 구간으로 이동하도록 
		else left = mid + 1;
	}

	// 결정 문제를 만족시키는 x의 최솟값 구하기 
	cout << ans;

	return 0;
}

프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스에 있는 동일한 문제는 if(sum > n) break; 없이도 정답 처리가 된다.

단, long long 타입의 변수 right을 초기화 할 때는 times 배열의 원소와 n이 모두 int형이므로 적어도 하나를 long long형으로 바꾸고 곱셈 연산을 해야 타입 캐스팅에서 오류가 발생하지 않는다. 1LL은 값이 1인 long long 타입의 숫자를 의미한다. 앞에 (long long)을 써서 명시적 캐스팅을 해도 된다.

#include <string>
#include <vector>
#include <algorithm>
typedef long long ll; 
using namespace std;

bool decision(vector<int> times, int n, ll mid){
    ll sum = 0;
    for(int i = 0; i < times.size(); i++){
        sum += mid / times[i];
    }
    return sum >= n;
}

ll solution(int n, vector<int> times) {
    ll left = 1;
    int maxTime = *max_element(times.begin(), times.end()); 

    // long long형으로 명시적 캐스팅 필수!!!
    ll right = 1LL * maxTime * n;  
    ll ans = right; 
    
    while(left <= right){
        ll mid = (left + right) / 2;
        
        if(decision(times, n, mid)) {
        	ans = min(ans, mid); 
        	right = mid - 1; 
		}
        else left = mid + 1; 
    }
    
    return ans;
}