[백준] 11509 - 풍선 맞추기

 

https://www.acmicpc.net/problem/11509

 

 

입력되는 정수 N이 1,000,000 이므로, O(N) 시간에 풀 수 있는 방법을 찾아야 함. { 파이썬은 1초에 2천만 정도의 instruction 처리 가능}

 

문제 풀이 아이디어

• 높이에 따라 풍선 처리
  • 매 순간, 풍선을 터트릴 수 있는 높이의 화살이 있는지 확인
  • 있다면 해당 위치의 화살의 높이를 한 칸 낮춤
  • 없다면 화살을 해당 높이에 추가.

손으로 한 풀이

정답 코드

import sys
n = int(sys.stdin.readline().rstrip())
ballons = list(map(int, sys.stdin.readline().split()))
arrows = [0] * (1_000_000 + 1)

for i in range(n):
    if arrows[ballons[i]]>0:
        arrows[ballons[i]] -= 1
        arrows[ballons[i]-1] += 1
    else:
        arrows[ballons[i]-1]+=1

print(sum(arrows))