[백준] 3079 - 입국심사 (C++)

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

상근이와 친구들 M명이 입국심사대가 N개 있는 곳에서 심사를 하려고 한다. k번 심사대에서 심사하는 데 걸리는 시간은 T_k다. 한 심사대에서는 한 사람만 심사를 할 수 있고, 초기에 모든 심사대는 비어있다.

가장 앞에 서 있는 사람은 비어있는 심사대로 이동할 수 있다. 항상 이동을 해야하는 것은 아니고, 더 빠른 심사대의 심사가 끝나길 기다린 다음 그곳으로 가서 심사를 받아도 된다.

이때, 상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 1,000,000,000
• 1 ≤ T_k ≤ 1,000,000,000

 

심사하는 데 걸리는 시간  T_k의 최댓값은 1,000,000,000 × 1,000,000,000으로 int의 범위를 넘어가기 때문에 long long int를 사용해야 한다. T_k의 최댓값/최솟값을 구하기 위해 mx=0, mn=1e9+1로 둔다.

 

T_k를 매개변수로 두고, 조건에 맞는 최소 시간을 이분탐색을 적용해 찾아야 한다. left는 0으로, right는 T_k 중 최대 시간에 m을 곱한 값으로 둔다.

 

구한 최소 시간이 조건에 맞는지는 M명의 사람마다 심사가 끝나는 시간을 기록한다거나 하는 복잡한 방식을 사용하지 않아도 간단하게 확인할 수 있다. N번의 반복문을 통해 구한 최소 시간을 입국심사대의 심사 시간으로 나눠 몫을 다 더한 게 m보다 크거나 같으면 된다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, M 입력받기
2. T_k 입력받기 (최댓값과 최솟값 기록)
3. left=0, right=T_k의 최댓값 × m으로 놓고 이분탐색
   
   1. 정해진 mid 값으로 몇 명이 심사를 끝낼 수 있는지 구하기
      1. m보다 같거나 크면 시간을 줄이기 위해 r=mid-1로 두고 ans 값 갱신
      2. m보다 작으면 시간을 늘리기 위해 l=mid+1로 두기
4. ans 값 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해 보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

1~4회차

• l과 r을 심사하는 데 걸리는 시간의 최솟값/최댓값에 m을 곱해 n으로 나누고 1을 뺀/더한 값을 넣기 때문에 최솟값을 구하기 위한 ans를 10의 18 제곱에 1을 더한 값으로 초기화하고, int 대신 long long int를 사용해야 함
• l과 r 초기 값 수정 및 while 반복문 조건과 l과 r을 갱신하는 mid 값 수정

 

5회차

참고자료

• long long int의 범위는 -2⁶³ (-9,223,372,036,854,775,808) ~ 2⁶³ (9,223,372,036,854,775,807)로, 대략 10의 18 제곱 × 9까지의 수를 담을 수 있음
• n이 10의 5 제곱, m이 10의 9 제곱, T_k가 모두 1일 때 cnt의 값이 10의 22 제곱으로 long long int의 범위를 넘을 수 있기 때문에 for문 안에서 cnt 값이 m의 최댓값인 10의 9 제곱을 넘기는 경우 멈춰줘야 범위 안에서 계산이 가능함

long long int l=mn*m/n, r=mx*m;
while (l<=r) {
    long long int mid=(l+r)/2,cnt=0;

    for (int i=0; i<n; i++)
        cnt += mid/v[i];

    if (cnt>=m) {
        r=mid-1;
        ans = min(mid,ans);
    }
    else {
        l=mid+1;
    }
}

 

---

정답 코드

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

long long int n,m,x,mn=1e9+1,mx,ans=1e19;
vector<int> v;

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

    cin >> n >> m;
    for (int i=0; i<n; i++) {
        cin >> x;
        v.push_back(x);
        mx = max(x,mx);
        mn = min(x,mn);
    }

    long long int l=mn*m/n, r=mx*m;
    while (l<=r) {
        long long int mid=(l+r)/2,cnt=0;

        for (int i=0; i<n; i++)
            cnt += mid/v[i];

        if (cnt>=m) {
            r=mid-1;
            ans = min(mid,ans);
        }
        else {
            l=mid+1;
        }
    }

    cout << ans;
}