1 minute read

11509번 : 풍선 맞추기

문제 링크

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

문제 설명

큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다. 진솔이는 화살 가지고 노는 것과 사냥 연습하는 것을 좋아한다. 진솔이는 화살을 왼쪽에서 오른쪽으로 쏜다. 높이는 임의로 선택한다. 화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다. 화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다. 화살은 계속해서 가던길을 가는데 높이는 1 줄어든다. 그러므로 만약 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다.

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

입력

첫 번째 줄에는 정수 N(1 ≤ N ≤ 1 000 000)이 들어온다.

두 번째 줄에는 배열 Hi가 N개 들어온다.

각각의 Hi(1 ≤ Hi ≤ 1 000 000)는 i번째 풍선의 높이에 해당하며 왼쪽에서 오른쪽으로 나열되는 순서이다.

출력

첫 번째 줄 한줄에 최소한 필요한 화살의 개수를 출력한다.

문제 풀이

문제에 대한 해석을 그대로 하여 코드로 옮겼지만.. 결과는 시간초과로 실패하였다. 백준 같은 알고리즘 풀이 사이트는 확실히 시간 복잡도가 중요한 거 같다. 폐인은 배열에 있는 항목을 ‘del’ 메소드를 통해서 삭제하는데 이게 시간 복잡도가 O(n)으로 잡아먹는다. 단순히 while문이 O(log n)으로 생각해서 괜찮을 거라고 생각했는데 ‘del’이 많이 잡아먹었다.

두 번째 코드는 다른 사람 풀이를 참고하여 풀었는데 정답이였는데 비록 for문을 사용하였지만 화살의 높이 배열을 따로 만들어서 배열의 항목을 더하고 빼는 형식으로 하여 시간 복잡도면에서 더 유리했다.

# 첫번째, 내가 생각한 문제 풀이 : 시간 초과... ㅠㅠ

import sys

input = sys.stdin.readline

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

result = 1
last_num = H[0]
del H[0]

while len(H) > 0 : 
    if last_num >= 2 and last_num-1 in H:
        last_num -= 1
        del H[H.index(last_num)]
    else : 
        last_num = H[0]
        del H[0]
        result += 1

print(result)

# 두번째, 다른 사람 풀이를 참고한 문제 풀이

import sys

input = sys.stdin.readline

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

cnt = 0
height = [0] * 1000001

for i in H :
    if height[i] :
        height[i] -= 1
    else :
        cnt += 1
    height[i-1] += 1
    
print(cnt)

Comments

You May Also Enjoy