• Home
  • About
    • Jang photo

      Jang

      Jang's blog

    • Learn More
    • Email
    • Facebook
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

(ALGO) 백준 1561번 문제 - 놀이공원 문제(python)

15 Aug 2018

Reading time ~1 minute

백준 1561번 문제

그림

해설

이분 탐색을 살짝 응용한 문제다. N이 20억이기 때문에 N을 이용하려면 logN의 속도로 처리해야 하기 때문에, 이분 탐색이 적절할 것이라고 생각하면 될 것 같다.
놀이기구와 타는 애들과의 관계를 표로 잘 정리하면, 특정 시간 n(소스 코드에선 mid가 해당됨)에 애들을 여태까지 몇 명 태웠는지를 계산 할 수 있다. 이 시간을 이분 탐색을 이용해 바꿔가며 여태까지 태운 아이들의 명수와 N이 가장 가까운 시간을 뽑아내서, 정확히 N명을 태웠을 경우 어떤 놀이기구를 타는 지 확인하면 된다.

구현

N, M = map(int, input().split())
t = list(map(int, input().split()))

l = 1
r = 10**20
max_m = max_s = 0

while l <= r:
    mid = (l+r)//2
    s = sum((mid-1)//x + 1 for x in t)
    if s < N:
        if max_m < mid:
            max_m = mid
            max_s = s
        l = mid + 1
    else:
        r = mid - 1

for i, k in enumerate(t):
    if max_m % k == 0:
        max_s += 1
        if max_s == N:
            print(i+1)
            break


algorithm Share Tweet +1