백준 문제 풀이 - 풍선 맞추기 11509번

📜 문제 이해하기

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 256 MB 2634 974 737 39.286%
문제
큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다. 진솔이는 화살 가지고 노는 것과 사냥 연습하는 것을 좋아한다. 진솔이는 화살을 왼쪽에서 오른쪽으로 쏜다. 높이는 임의로 선택한다. 화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다. 화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다. 화살은 계속해서 가던길을 가는데 높이는 1 줄어든다. 그러므로 만약 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다.
우리의 목표는 모든 풍선을 터트리되 가능한한 적은 화살을 사용하는 것이다.

💡 문제 재정의

풍선이 각자 높이를 가지고 있다. 화살을 쏴서 풍선을 맞추면 높이가 1 줄어들 때 필요한 총 화살의 수를 구해라.

✏️ 계획 수립

화살의 높이를 전부 저장하는 배열을 가지고 있으면 된다.
총 1000000개의 배열을 가지고 있고 각 높이마다 필요한 화살이 있다면 1을 낮추고 없다면 추가하면 된다.

💻 계획 수행

import sys

n = int(sys.stdin.readline())
m = list(map(int, sys.stdin.readline().split()))
arrows = [0] * 1000001
count = 0

for i in range(n):
    if arrows[m[i]] == 0:
        count += 1
        arrows[m[i]-1] += 1
        
    else:
        arrows[m[i]] -= 1
        arrows[m[i]-1] += 1
    
print(count)

🤔 회고

공간 복잡도를 버리고 시간 복잡도를 빠르게 할 수 있어 동적계획법으로 문제 분류를 잡았다.