백준 1561 - 놀이 공원 (Python)

boj.kr/1561

 

일단 숫자 크기를 보니 O(n)으로는 절대 안 된다는 건 알겠다. 그래서 내린 결론은? 이분탐색

 

인데... 뭘 기준으로 이분탐색을 진행할지 고민을 많이 했던 것 같다.

 

일단 결론은 모든 놀이기구를 타는 시간을 기준으로 해결하였다.

 

minT=0
maxT=n*max(times) # 놀이기구 타는 최대 시간

 

최대 시간을 어떤 식으로 잡을까 하다가 n명이 가장 시간이 오래 걸리는 놀이기구 max(times)를 탄다고 생각하면 될 것 같아 n*max(times)로 최대 시간을 표현해보았다.

 

그다음엔 n명을 처리가능한 최소 시간을 찾아보겠다. 물론 이분탐색으로 찾는 거다.

 

retT=0 # n명 처리 가능한 최소 시간

while minT<=maxT:
    midT=(minT+maxT)//2

    tempNo=0 # 처리 가능한 사람 수
    for t in times:
        tempNo+=((midT//t)+1)
    
    if tempNo<n:
        minT=midT+1
    else:
        maxT=midT-1
        retT=midT

 

여기에서 핵심 포인트는 처리 가능한 사람 수를 찾는 로직인데, 첨에 생각할 때는 예상 처리 시간(midT)에 시간(t)으로 나누면 놀이기구를 몇 번 탈 수 있을지 구할 수 있을거라 생각했다.

 

그런데 만약 전체 시간 10에 시간 3짜리 놀이기구를 몇번 탈 수 있나 생각해 보면 0 -> 3 -> 6 -> 9 : 총 4번 탈 수 있는거다. 왜냐하면 0초에 탑승해서 9초에 끝나자마자 또 다음 잼민이가 탑승하기 때문이다.

 

시간 10에 시간 2짜리 놀이기구를 생각해보면 0 -> 2 -> 4 -> 6 -> 8 -> 10 : 총 6번이다. 시간 10에 못 타지 않나요?라고 생각할 수 있긴 한데 놀랍게도 10 되면서 바로 다음 잼민이가 탑승하기 때문이다.

 

이렇게 이분탐색을 사용해 n명 처리 가능한 최소 시간 retT를 구해준다.

 

자 이제 구해진 최소 시간 retT로 다음 잼민이가 어떤 기구를 타는지 구해야 하는데, 여기에서 개인적으로 고민을 많이 했었다.

 

retT일 때 n만큼 타는 거면? -> retT-1일 때의 상태를 구해서 거기서 1만큼의 시간이 지났을 때 어떤 놀이기구에 탈 수 있는지를 앞에서부터 확인(더 작은 번호의 놀이기구 먼저 탄다고 했으니까...) 해주면 되는 것이다!

 

tempNo=0 // 현재 처리한 사람 수
for t in times:
    tempNo+=(((retT-1)//t)+1)

 

그래서 일단 시간이 retT-1일 때 처리한 사람 수를 구해준다. 해당 로직은 위에서 이분탐색할 때 사용했던

tempNo=0 # 처리 가능한 사람 수
for t in times:
    tempNo+=((midT//t)+1)

 

이 로직과 같다.

 

그리고 이제 시간을 처음부터 확인하며 현재 탈 수 있는 놀이기구가 뭔지 검사한다.

 

for i in range(m):
    if retT%times[i]==0:
        tempNo+=1
    if tempNo==n:
        print(i+1)
        break

 

현재 시간 retT를 놀이기구 운행시간 times [i]로 나누어지면 탑승 가능하다는 의미이므로 현재 탑승 인원 tempNo를 1 더해준다. 그런데 방금 탑승한 사람이 n번째 사람이면 놀이기구 번호를 출력해 준다. 참고로 놀이기구 번호는 0이 아니라 1부터 시작이므로 1 더해서 출력해 주었다. 그리고 break.

 

이분탐색을 풀 때 항상 느끼는 건데 일단 최소, 최대 범위를 정하기가 까다로운 것 같다. 그리고 이 문제는 구해진 파라미터를 어떻게 활용해야 정답을 도출할 수 있을지 고민을 많이 했던 문제다.

 

전체 코드

 

import sys

input=sys.stdin.readline

n,m=list(map(int,input().split()))

times=list(map(int,input().split()))

minT=0
maxT=n*max(times) # 놀이기구 타는 최대 시간

retT=0 # n명 처리 가능한 최소 시간

while minT<=maxT:
    midT=(minT+maxT)//2

    tempNo=0 # 처리 가능한 사람 수
    for t in times:
        tempNo+=((midT//t)+1)
    
    if tempNo<n:
        minT=midT+1
    else:
        maxT=midT-1
        retT=midT

# retT 만큼은 있어야 n명 처리 가능
# retT-1 일때는?

tempNo=0
for t in times:
    tempNo+=(((retT-1)//t)+1)

for i in range(m):
    if retT%times[i]==0:
        tempNo+=1
    if tempNo==n:
        print(i+1)
        break