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

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

11509번: 풍선 맞추기

이 문제는 어떻게하면

화살을 적게 쓰고

풍선을 다 터트릴 수 있는가를 묻고 있습니다.

이 문제는 정렬을 절대 쓰면 안 됩니다.

화살의 조건을 보면

정렬을 잘못쓰면

문제의 상당부분이 틀어저버리죠.

정답 코드에 앞서,

제가 처음 풀었던 오답코드를 보겠습니다.

#백준 11509번 풍선 맞추기

N=int(input())
ballons=list(map(int,input().split()))

answer=1
now=ballons[0]
for i in range(1,N):
    if now<ballons[i]:
        answer+=1
    now=ballons[i]
print(answer)

첫번째 풀이의 논리는 이렇습니다.

이렇게 풀면 당연히 틀렸다고 뜹니다.

반례는 이렇습니다.

 

5

3 1 5 4 3

 

위의 풀이대로 간다면

2가 나올테지만

정답은 3입니다.

 

화살은 풍선을 터트리면 한칸 아래로 갑니다.

3을 보고 던진 화살은

떨어지면 2가 됩니다.

그러면 3 다음의 1은 터트리지 못하죠.

그래서 1을 터트릴 때는

새로운 화살이 필요합니다.

이후 5에서 화살을 던지면

차례대로 5 4 3이 터지니

총 3개가 필요한 거죠.

 

그래서 문제에서 주어진 화살의 조건을 보고

풀이를 완성했습니다.

#백준 11509번 풍선 맞추기

N=int(input())
ballons=list(map(int,input().split()))

answer=0
visited=[False]*N

for i in range(N):
    #아직 안터트린 풍선 포착
    if visited[i]==False:
        visited[i]=True
        answer+=1
        allow=ballons[i]-1
        #풍선을 포착하고 그 높이에서 던진다.
        for x in range(i+1,N):
            if allow==0:
                break
            if ballons[x]==allow and visited[x]==False:
                visited[x]=True
                allow-=1

print(answer)

 

문제를 풀 때

길찾기 문제가 생각이 나더라고요.

visited를 N만큼 선언한 뒤에

왼쪽부터 탐색합니다.

아직 visited가 False인 상태면

아직 풍선이 있는 상태이니

화살을 던져줍니다.

제가 allow=ballons[i]-1로 한 건

그 다음부터의 화살은

지금 터트린 풍선에서 높이가 1 줄어들어서 입니다.

그렇게 화살을 이동시키면서

화살이 풍선의 높이와 같다면

visited를 True로 바꿔주고

allow의 높이를 1 낮춰줍니다.

0이 되면 땅에 떨어진 경우이므로

더이상 탐색하지 않고 break시켜줍니다.

 

문제의 조건에 따라

차근차근 구현해주면

풀릴 수 있는 편이라

그리디 알고리즘중에서는

체감난이도가 높지는 않았네요.