김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 1561 놀이 공원 파이썬(Python)

문제 링크

이분 탐색(Binary Search, 이진 탐색) 문제.
\(N \le 2 \times 10^{9}\)이므로 선형 시간 복잡도로는 풀 수 없다는 것을 쉽게 알 수 있다.
h분 기다렸을 때, 지금까지 놀이기구에 탄 아이들의 수는 h를 모든 놀이기구의 운행 시간으로 나눈 값의 합이다.
이를테면, 놀이기구가 10분짜리 하나라면, 100분 동안 10명의 아이들이 놀이기구에 탑승했을 것이다.
만약 놀이기구가 10분짜리 하나, 8분짜리 하나라면 100분 동안 24명의 아이들이 놀이기구에 탑승했고(\(100 \div 10 + 100 \div 8 = 24\)), 10분짜리 놀이기구는 자리가 비었을 것이고(\(100 \mathrm{mod} 10 = 0\)), 8분짜리 놀이기구는 4분 후에 가용할 것이다(\(100 \mathrm{mod} 8 = 4\)).
그런 논리로, 마지막 아이가 놀이기구에 탈 때까지 걸리는 시간을 계산해줄 수 있다.
이분 탐색으로 놀이기구에 탑승한 아이들의 수가 N 이상이 되는 시간 p를 찾아내면 되기 때문이다.
그러면 다시 그 p를 가지고 p분 기다렸을 때 몇 명이 놀이기구를 탔는지, 그리고 p분째에 가용한 놀이기구가 어떤 것들인지 알 수 있다.
이제 그 놀이기구들을 번호가 빠른 것부터 봐서 N번째 아이가 타는 놀이기구를 찾으면 된다.
이렇게, 이분 탐색으로 특정 조건을 만족하는 최대/최솟값을 구하는 알고리즘을 파라메트릭 서치(Parametric Search)라고 한다고 한다.

#!python

# n번째 학생이 몇 분 후에 놀이기구에 타게 되는지 구하는 함수
# 이때, k는 이분 탐색을 위한 상한
def get_position(nums, n, k):
    left, right = 0, k
    while left <= right:
        mid = (left + right) // 2
        if sum(map(lambda x: mid // x, nums), m) < n:
            left = mid + 1
        else:
            right = mid - 1
    return left

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

# 이분 탐색의 상한
# 시간이 h인 놀이기구 하나만 있을 때, 마지막 아이가 n * h 분 후에 놀이기구에 타게 되는 것은 자명하다
# 거기서 놀이기구가 추가된다면, 마지막 아이가 기다리는 시간이 줄어들면 줄어들었지, 늘어나진 않을 것이다
# 따라서 n * min(nums)를 상한으로 할 수 있다
k = n * min(nums)

# p는 마지막 아이가 놀이기구를 탈 때까지 기다리는 시간
p = get_position(nums, n, k)
# cur는 p분째에 놀이기구를 타는 아이의 번호
cur = sum(map(lambda x: (p - 1) // x, nums), m)
for i, num in enumerate(nums):
    # p가 num으로 나눠떨어지는 경우에만(즉, p분째에 놀이기구가 가용한 경우에만)
    if p % num:
        continue
    
    # 놀이기구에 아이를 태우므로 번호가 1 증가
    cur += 1

    # n번째 아이가 탑승하면 탑승한 놀이기구의 번호 출력하고 종료
    # i는 0부터 시작했으므로 +1을 해준다
    if cur != n:
        continue
    print(i + 1)
    break

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑