[Baekjoon] 14493 [과일노리] 입맛대로 문제풀이

카테고리

• 수학, 구현, 시뮬레이션

import sys
input = sys.stdin.readline

# 장애물 개수
N = int(input())

total = 0
for n in range(N):
    a, b = map(int, input().split())
    cycle = a + b
    r = total % cycle
    # 현재 감시중인 경우 -> b까지 기다려야 함.
    if r < b:
        total += (b - r)
    total += 1

print(total)

문제를 풀때 복잡하게 생각했는데, 생각외로 간단하다… $O(N)$의 시간복잡도로 해결할 수 있는데, 입력을 다 해놓고 고려하는 것이 아닌, 입력을 하면서 고려하는 방법을 사용했다.

각 장애물의 주기가 A/B가 있다면, A+B초 주기로 반복되며, 매 주기에서 처음 B초 동안은 감시가 진행된다. (시작과 동시에 감시 진행) 현재 시간을 total로 잡으면, 그 장애물 주기 내 위치는 r = t % (a+b)로 계산이 가능하다.

여기서 만약, r < b라면, 아직 감시가 진행중이므로, 남은 감시 기간은 b-r초동안 기다려야 한다. 그 다음에, 이제 장애물을 통과하는데 1초가 걸리므로 1초만 더해주면 된다.

이렇게 진행하면 $O(N)$의 시간복잡도로 문제를 해결할 수 있다.

단, 처음 생각할 때, 너무 많이 생각했어서 $O(N^2)$로 풀어서 시간초과가 났었는데… 생각보다 단순하게 생각했으면…