11509번: 풍선 맞추기
첫 번째 예제 에서 [5,4,3] 을 터트리고 [2,1]을 터트리면 모든 풍선을 터트릴 수 있으므로 최소한 2개의 화살을 필요로 한다.
www.acmicpc.net
약간 애를 먹었다.
구현 핵심 아이디어를 초반에 생각했다가 다른 방법으로 풀었는데 시간초과가 발생했다.
구현 방식을 O(N) 으로 변경해서 다시 구현했는데 이번엔 실수로 한참 헤맸다.
N = int(input())
ballons = list(map(int, input().split()))
flag = [0] * 1000001
ans = 0
for i in range(len(ballons)):
if flag[ballons[i]] == 0:
ans+=1
flag[ballons[i] - 1] += 1
else:
flag[ballons[i]] -= 1
flag[ballons[i] - 1] += 1
print(ans)
# 5
# 4 5 2 1 4
# 5
# 2 1 5 4 3
핵심 아이디어는 아래와 같다.
우선 O(N)에 부합하기 위해 풍선의 제한수인 100만의 크기를 가지는 flag 배열을 생성한다.
그리고 발사된 화살의 위치를 flag 배열에 저장한다.
예를들어 [4,5,2,1,4] 의 경우
전체 풍선을 처음부터(왼쪽부터) 순회하면서 각 풍선의 위치를 확인한다.
1. 첫 풍선을 보니 위치 4에 있고 해당위치에 화살이 있는지 확인(flag 의 해당위치(인덱스) 값이 0이 아닌지) 한다.
해당위치에 화살이 없으므로(flag 의 해당위치(인덱스) 값이 0이므로) 화살을 발사해야하며 결과값에 1을 추가하고 발사된 화살은 4를 맞췄으니 1을 빼준 3의 위치에 있다는 것을 flag 배열에 기록한다. -> [0, 0, 0, 1, 0, 0, 0, 0, 0, 0] ans:1
2. 두번째 풍선을 보니 위치 5에 있고 해당위치에 화살이 있는지 확인(flag 의 해당위치(인덱스) 값이 0이 아닌지) 한다.
해당위치에 화살이 없으므로(flag 의 해당위치(인덱스) 값이 0이므로) 화살을 발사해야하며 결과값에 1을 추가하고 발사된 화살은 5를 맞췄으니 1을 빼준 4의 위치에 있다는 것을 flag 배열에 기록한다. -> [0, 0, 0, 1, 1, 0, 0, 0, 0, 0] ans:2
3. 세번째 풍선을 보니 위치 2에 있고 해당위치에 화살이 있는지 확인(flag 의 해당위치(인덱스) 값이 0이 아닌지) 한다.
해당위치에 화살이 없으므로(flag 의 해당위치(인덱스) 값이 0이므로) 화살을 발사해야하며 결과값에 1을 추가하고 발사된 화살은 2를 맞췄으니 1을 빼준 1의 위치에 있다는 것을 flag 배열에 기록한다. -> [0, 1, 0, 1, 1, 0, 0, 0, 0, 0] ans:3
4. 네번째 풍선을 보니 위치 1에 있고 해당위치에 화살이 있는지 확인(flag 의 해당위치(인덱스) 값이 0이 아닌지) 한다.
해당위치에 화살이 존재하므로(flag 의 해당위치(인덱스) 값이 1이므로) 화살은 1을 맞추고 1을 빼준 0의 위치에 있다는 것을 flag 배열에 기록한다. -> [1, 0, 0, 1, 1, 0, 0, 0, 0, 0] ans:3
(0의 위치에 있다는건 화살이 떨어졌다는것이다. 풍선의 위치 H의 최소값은 1이므로 0 위치에 있는 화살은 더이상 어떤 풍선도 맞추지못한다)
4. 다섯번째 풍선을 보니 위치 4에 있고 해당위치에 화살이 있는지 확인(flag 의 해당위치(인덱스) 값이 0이 아닌지) 한다.
해당위치에 화살이 존재하므로(flag 의 해당위치(인덱스) 값이 1이므로) 화살은 4을 맞추고 1을 빼준 3의 위치에 있다는 것을 flag 배열에 기록한다. -> [1, 0, 0, 2, 0, 0, 0, 0, 0, 0] ans:3
** 위치 3에는 현재 두개의 화살이 떠있다. 그러므로 위치 3에서 풍선을 두번만나도 화살을 발사하지 않아도 된다. (이 부분을 실수해서 조금 헤맸다)
결과는 3이다.