[백준] 3079 : 입국심사 (Python)

 

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

 

 

---

 

아이디어

해당 문제는 결론부터 말하자면, 이분 탐색 유형이다. 필자의 순차적 사고 과정을 작성하였으므로, 사고의 흐름을 파악하면 문제 접근에 도움이 될 것이다.

 

완전 탐색 1 : 그래프(BFS)

루트 노드를 기점으로, BFS를 통해 모든 경우를 비교하여 정답을 카운팅하는 알고리즘을 처음 생각했다. 상황 그래프이기 때문에, 메모리 공간과 시간은 2의 거듭제곱의 복잡도를 가지므로 해당 알고리즘을 탈락시켰다.

 

완전 탐색 2 : 그리디(탐욕)

갱신되는 각 심사대의 끝 시간을 기준으로, 가장 빨리 다음 손님을 받는 심사대를 탐욕적으로 선택하는 방법을 고안하였다. 1번째 예제입력 케이스를 바탕으로 알고리즘 과정을 설명한다. 다음의 사진을 보자.

1번 예제에 대한 타임라인. 상근이와 친구들을 넘버링하여 배치

다음의 사진은 이 타임라인에 각 친구들을 배치하는 과정을 나타내었다.

1번케이스 정답인 28까지의 프로그램 연산 과정

• machine(심사대) 딕셔너리 초기세팅 : {7:0, 10:0}
  • (key, value) = (각 심사대 시간, 현재 입장 가능한 시간==기존 사람의 심사가 끝나는 시간)
• 1번째 친구 입장 : d[7]에 배치 -> {7:7, 10:0}
• 2번째 친구 입장 : d[10]에 배치 -> {7:7, 10:10)
• 3번째 친구 입장 : min(14, 20) -> 7초 심사대가 더 적은 시간이므로, d[7] 선택.
  • d 갱신 : {7:14, 10:10}
• ...

이런식으로, 진행되고 마지막 6번째일때 어떤 심사대를 선택했는지를 통해 최종적으로 갱신된 d[7]을 정답으로 출력하는 것이다. 그러나, 시간복잡도를 계산하게 되면, n번의 반복 내에서 최소의 딕셔너리값을 찾기 때문에 다음과 같이 표현할 수 있다.

• O(n * m) == O(n * n)

문제에서 n과 m의 최대 입력값이 엄청 큰 정수값이 들어오기에, 해당 시간복잡도로는 시간 초과의 가능성이 높다. 그러므로, 해당 알고리즘 설계를 탈락시켰다.

 

발상의 전환

그리드 방식까지 공통된 핵심 아이디어는 다음과 같았다.

• 상근이와 친구들을 어떻게 타임라인에 배치시켜야 하는가?

우리는 O(n * n) 보다 적은 O(log n) ~ O(n) 범위 내의 알고리즘 기법을 설계해야 하는 것이 목표이다. 이를 바탕으로, log n에 해당되는 탐색 기법인 이분 탐색을 떠올려 볼 수 있다. 이에 적용시키기 위해 핵심 아이디어를 다음과 같이 전환하면 설계를 진행할 수 있다.

• 특정 시간을 기준으로 몇명이 심사를 받고 있는가?

이를 이용하여 어떻게 left,right 및 mid를 설정하고 각각이 무엇을 의미하는지 차근차근 알아보자.

 

O(log n)의 시간이 걸리는 이분 탐색

먼저, left와 right를 설정해야 한다. 우리가 탐색하고자 하는 정답은 시간이므로,  left와 right는 최소 최대로 심사가 걸리는 시간이 될 것이다. 이를 통해 다음과 같이 정의할 수 있다.

• arr : 심사대의 각 시간이 담겨있는 1차원 배열
• Left : 1명이 심사를 받는 최소 시간. min(arr)
• Right : m명이 심사를 받는 최대 시간. max(arr) * m

즉, Left ~ Right 시간 범위에서 Left에 가까운 특정 시간을 찾는 것이 우리의 목표가 되는 것이고, 이 특정 시간은 mid값으로 설정하여 진행하면 된다.

 

그렇다면, 탐색 구간(Left ~ Right)를 어떤 식으로 갱신을 해야 할까? 예제 입력 2번 케이스를 통해 알아보자. 특정 시간인 mid를 6이라고 가정해보고, 다음의 사진을 보자.

예제 입력 2번 케이스의 정답 타임라인.

이 타임라인에 우리는 특정 시간 6인 mid값을 이용해야 한다. 즉, '6초까지 몇 명이 심사를 받을 수 있는가?'를 통해 탐색 구간의 갱신 조건을 설정할 수 있다. 다음의 사진은 이 생각을 시각화한 것이다.

타임라인 중 6초에 해당되는 열에 세로선 추가

6초까지 총 몇명이 심사를 받고 있는지에 대한 total명을 알게 되면, 이를 바탕으로, 탐색 구간을 재설정할 수 있다.

• Total >= m
  • 모든 인원이 심사를 받기 충분한 시간(mid)이다. (심사를 마친 몇 명이 재밌다고 다시 재심사하러 갈 수 있는 정도..)
  • 해당 특정 시간(mid)는 모든 인원이 심사를 받을 수 있으므로, answer 갱신. (초기 answer는 당연히, right값이 된다.)
  • 이후, 이보다 더 작은 시간에서도 모든 인원이 심사를 받을 수 있는지 탐색 필요.
  • right = mid - 1로 갱신.
• Total < m
  • 몇 명의 인원들은 아직 심사 대기 중이라는 의미.
  • 해당 시간보다 큰 쪽으로 탐색 진행 필요.
  • Left = mid + 1

이러한 갱신 조건을 바탕으로, Left > Right가 될 때까지 탐색을 진행하다 보면, 결국 모든 인원이 심사를 받는 최소의 시간을 O(log n)의 시간 복잡도로 구할 수 있게 된다.

 

정답 코드

# https://www.acmicpc.net/problem/3079
# 입국심사
# 이분탐색

input=__import__('sys').stdin.readline

n,m=map(int,input().split())
T=[int(input()) for _ in range(n)]

left,right=min(T),max(T)*m
answer=right

while left<=right:
    mid=(left+right)//2
    total_cur_possible=sum(mid//T[i] for i in range(n))
    
    if total_cur_possible>=m:
        answer=min(answer,mid)
        right=mid-1
    else:
        left=mid+1

print(answer)