백준[1561] 놀이 기구 (Python3)

완전 탐색

매 분마다 놀이 기구들의 남은 시간을 확인한다.
이 경우 N = 2,000,000,000, M = 1, M[0] = 30 인 경우 60,000,000,000번의 연산이 필요해 시간 초과가 발생한다.

완전 탐색 최적화

연산 횟수를 줄이기 위해선 탐색하는 빈도를 줄이는 방향으로 갔다.
관찰 결과 아이들이 M 명 이하로 남았을 때를 보면 된다 생각했다.
그중에서도 모든 아이들이 놀이 기구를 타기 직전의 상황을 보면 더 빠르게 문제를 해결할 수 있다고 생각했다.

이분 탐색

임의의 시간 X에 놀이 기구 A는 a 번을 타고, B는 b 번을 타는 식으로 해서 Z는 z 번을 탄다.
이 a + b + c + ... + z를 더한 뒤 아이들의 전체 수인 N과 대소를 비교한다.
시간 X를 정할 때, 최악의 경우 60,000,000,000분의 대기 시간이 필요하기 때문에 이분 탐색을 통해 대기 시간의 탐색 범위를 절반씩 줄인다.
log(60,000,000,000) = 35.x이므로, 36번이면 최적의 X를 찾을 수 있다.

탐색한 X마다 해당 시간이 될 때 몇 명의 아이들이 놀이 기구를 탈 수 있는지 확인한다.
X를 해당 놀이 기구의 대기 시간을 나눈 몫 + 1을 더해 나간다.

모든 놀이 기구에 대해 확인을 해야 하므로, 매 이분 탐색마다 M 만큼의 탐색이 발생하니
log(60,000,000,000) * M(10, 000) 즉, 36 * 10,000 만큼의 시간 복잡도가 발생하는 것을 알 수 있다.

시간 X에 대해 N 명의 아이들이 다 탈 수 없다면, left 값을 늘리고, N 명 이상의 아이들이 탈 수 있다면, right 값을 줄이면서, 해당 시간을 기억해 둔다.

시간 X를 구한 후

우리가 볼 것은 맨 마지막 아이가 타는 놀이 기구 번호이므로, X의 1분 전에 몇 명의 아이들이 남았는지를 확인한다.
그 후, 원래 시간 X에 대해 놀이 기구의 대기 시간이 도는 경우(X % M == 0)를 체크해, 남은 아이들을 카운팅 한다.
이 과정에서 남은 아이들이 더 이상 없다면 해당 놀이 기구의 인덱스를 출력한다.

 

코드

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


def main():
    if N <= M:
        print(N)
        return
    left, right = 0, 2000000000000000
    while left <= right:
        mid = (left + right) // 2
        ret = calcTotal(mid)
        if ret >= N:
            right = mid - 1
            time = mid
        else:
            left = mid + 1
    print(getAnswer(time))


def calcTotal(mid):
    total = M
    for ride in rides:
        total += mid // ride
    return total


def getAnswer(mid):
    human = M
    for i in range(M):
        human += (mid - 1) // rides[i]
        if human == N:
            return i + 1

    for i in range(M):
        if mid % rides[i] == 0:
            human += 1
        if human == N:
            return i + 1



if __name__ == '__main__':
    main()