[baekjoon] 백준 11509번(파이썬): 풍선 맞추기

문제

11509번: 풍선 맞추기

- 큰 방에 N개의 풍선이 떠있다.

- 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다.

- 진솔이는 화살 가지고 노는 것과 사냥 연습하는 것을 좋아한다.

- 진솔이는 화살을 왼쪽에서 오른쪽으로 쏜다.

- 높이는 임의로 선택한다.

- 화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다.

- 화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다.

- 화살은 계속해서 가던길을 가는데 높이는 1 줄어든다.

- 그러므로 만약 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다.

- 우리의 목표는 모든 풍선을 터트리되 가능한한 적은 화살을 사용하는 것이다.

- 풍선, 정수 N(1 ≤ N ≤ 1 000 000)이 들어온다.

- 배열 H가 N개 들어온다. 각각의 H(1 ≤ H ≤ 1 000 000)는 i번째 풍선의 높이에 해당하며 왼쪽에서 오른쪽으로 나열되는 순서이다.

알고리즘

- 풍선의 개수를 입력받는다.

- 풍선이 있는 화살의 높이를 입력받는다.

- 발사의 유무를 확인하기 위해 풍선의 개수만큼 리스트를 만든다.

- 화살의 높이를 확인한다.

- 화살이 발사 되어있으면 똑같은 화살로 풍선을 터트리고 화살의 높이를 내려 다시 조준한다.

- 화살이 발사 되어있지않으면 풍선을 터트리고 화살의 높이 -1 위치에 화살을 조준한다.

코드

import sys


n = int(sys.stdin.readline())
h = list(map(int, sys.stdin.readline().split()))
# 발사된 각 화살의 높이
cnt = [0] * (n + 1)

# 화살의 높이를 확인한다.
for i in h:
    # 화살이 발사되어있으면 똑같은 화살로 풍선을 터트리고 화살의 높이를 내린다.
    if cnt[i] > 0:
        # 풍선을 터트리고 원래 화살을 빼주고
        # 화살의 높이 -1 위치에 화살을 다시 조준한다.
        cnt[i] -= 1
        cnt[i - 1] += 1
    else:
        # 화살이 발사되지 않았으므로
        # 풍선을 터트리고 화살의 높이 -1 위치에 화살을 조준한다.
        cnt[i - 1] += 1

# 발사된 화살의 개수를 출력한다.
print(sum(cnt))

github

junjange/CodingTest