사용자 도구

사이트 도구


ps:problems:boj:2346

풍선 터뜨리기

ps
링크acmicpc.net/…
출처BOJ
문제 번호2346
문제명풍선 터뜨리기
레벨실버 3
분류

기초

시간복잡도O(n^2)
인풋사이즈n<=1000
사용한 언어Python
제출기록32424KB / 84ms
최고기록56ms
해결날짜2022/04/24
태그

[라이] 리스트/배열/연결 리스트

풀이

  • 요세푸스 문제와 비슷한 문제. 이동해야 하는 값이 고정되어있지 않고 계속 바뀐다는 것만 다르다.
  • Order Statistic Tree를 사용해서 O(nlogn)에 풀수 있지만, n이 작다보니 그냥 덱을 이용해서 O(n^2)에 풀어도 빠르게 풀린다. 나도 그냥 덱을 이용해서 풀었다.

코드

"""Solution code for "BOJ 2346. 풍선 터뜨리기".

- Problem link: https://www.acmicpc.net/problem/2346
- Solution link: http://www.teferi.net/ps/problems/boj/2346
"""

import collections


def main():
    N = int(input())
    baloons = collections.deque(range(1, N + 1))
    nums = [int(x) for x in input().split()]
    for _ in range(N):
        popped_baloon = baloons.popleft()
        print(popped_baloon, end=' ')
        rot = -nums[popped_baloon - 1]
        if rot < 0:
            rot += 1
        baloons.rotate(rot)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
U Y​ D Q X
 
ps/problems/boj/2346.txt · 마지막으로 수정됨: 2022/05/03 07:07 저자 teferi