BOJ15235

Olympiad Pizza

최근에 시간 초과에 하도 쳐맞다 보니 시간복잡도부터 생각하는 버릇이 생겼다. N이 1000이고, 모든 수가 1000이라면 그냥 요세푸스문제0인가 풀 때처럼 다 돌아도 100만번 밖에 연산이 돌지 않으므로 이게 맞는 풀이일 것이라고 생각했다. 근데 제한 조건에 대해서 고민하던 중 while 위에 sum(arr)라는 부분을 사용했는데 이게 문제가 될 수도 있겠다는 생각이 들긴 하였다. 그래도 뭐 100만번에 2초면 아주 여유 있다는 생각에 우선 생각한대로 코드를 짜고 제출하였다.

import sys

N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
ans = [0 for _ in range(N)]
i = 0
cnt = 0

while sum(arr) != 0: # 종료 조건
    if arr[i] == 0:
        i += 1
        i = i % N
        # 0개면 더 이상 먹을 필요 없으니 PASS
    else:
        arr[i] -= 1
        cnt += 1
        if arr[i] == 0:
            ans[i] = cnt
        i += 1
        i = i % N
        # 1개 이상이면 먹고 0개가 되는 시간을 포착하기 위한 조건문 추가

print(*ans)

EASY! 솔직히 티어는 요세푸스 0 문제와 동일하게 측정해야 한다고 생각했다. 그냥 이 문제는 그나저나 자료구조 문제인데 잘 만든 웰메이드 문제긴 한 것 같다.
Tier : 실버 4
TC :

1
100
OUT : 100
1000
1000 ...
OUT : 999901 999902 ...

그나마 엣지라고 생각할 수 있을만한 부분들만 정리해보았다.