[백준] 11509 - 풍선 맞추기 / Python / 골드 5

🚩문제 주소

📄풀이

가장 큰 수부터 내려가는게 가장 빠르기 때문에 max값과 인덱스를 저장해줍니다.

maxIdx부터 끝까지 반복을 해주는데, 현재 위치에 있는 값이 max값과 같다면 max값을 -1 해주고 max값을 0으로 바꿔줍니다.

반복이 끝나면 쏜 화살의 갯수를 1 증가시킵니다.

풍선의 max값이 0 이라면 모두 쏜 것이므로 반복을 종료한 후 정답을 출력합니다.

Ex) 4 5 2 1 4

• Shot 1: 5 2 1 4, max = 5 ➡ 0 2 1 4, max = 4 ➡ 0 2 1 0, max = 3
• Shot 2: 4 0 2 1 0, max = 4 ➡ 0 0 2 1 0, max = 3 ➡ 3이 없으므로 종료
• Shot 3: 2 1 0, max = 2 ➡ 0 1 0, max = 1 ➡ 0 0 0, max = 0 ➡ max가 0이므로 정답 3

👨‍💻코드

n = int(input())
ballon = list(map(int, input().split()))
shot = 0

while True:
  maxIdx = ballon.index(max(ballon))
  maxBallon = max(ballon)

  if maxBallon == 0: break

  for i in range(maxIdx, len(ballon)):
    if ballon[i] == maxBallon:
      maxBallon -= 1
      ballon[i] = 0
  shot+=1

print(shot)