[프로그래머스] 풍선 터트리기 - python

https://school.programmers.co.kr/learn/courses/30/lessons/68646

프로그래머스

난이도: Lv3
알고리즘: DP

 

풀이과정

---

우선 입력으로 주어지는 a의 길이를 보면 `1,000,000`으로 매우 큰 크기의 배열이 들어온다.

 

그렇다면 우리는 a의 각 풍선을 순회하며 해당 풍선이 마지막에 남을 수 있는지의 여부를 O(1) 또는 O(log n) 시간에 판단해야 한다.

 

DP를 사용하면 O(1) 시간에 각 풍선이 마지막에 남을 수 있는지를 알 수 있다.

 

입출력 예인 `[-16,27,65,-2,58,-92,-71,-68,-61,-33]`를 통해 어떻게 DP로 풀 수 있는지 알아보자.

 

먼저 첫 번째 풍선과 마지막 풍선은 항상 마지막까지 남길 수 있다.

 

첫 번째 풍선을 남기는 방법은 첫 번째 풍선 이후의 풍선끼리 선택하여 큰 풍선을 계속해서 터뜨린다. 위 예제에서는 첫 풍선인 `-16`과 가장 작은 수의 풍선인 `-92`가 남을 것이다. 이때 번호가 작은 풍선을 터뜨릴 수 있는 기회가 아직 한 번 남아있으므로 `-92`가 적힌 풍선을 터뜨려 `-16` 번호가 적힌 풍선을 남길 수 있다.

 

같은 방법으로 마지막 풍선은 `-92`와 `-33`이 남게 되고 역시 번호가 작은 풍선을 터뜨릴 수 있는 기회가 한 번 남아있으므로 `-92`번이 적힌 풍선을 터뜨려 마지막 풍선이 남도록 할 수 있다.

 

그렇다면 중간에 있는 풍선을 남길 수 있는 경우를 생각해보자. 남기고자 하는 풍선의 좌 우 풍선들을 먼저 터드려서 3개의 풍선만 남긴다. 그리고 중간의 풍선을 남길 수 있는지 확인해보면 된다.

 

만약 `58`번을 남길 수 있는지 확인하자면 좌 우의 풍선들을 선택하고 먼저 터뜨려 `[-16, 58, -92]`가 남도록 한다. 하지만 `-16`과 `-92`가 모두 `58`보다 작으므로, 작은 풍선을 두 번 터트려야 `58`번 풍선을 남길 수 있다. 따라서, 이 경우에는 `58`번이 적힌 풍선을 남길 수 없다.

 

하지만 `-71`번이 적힌 풍선은 `[-92, -71, -68]`이 남게되고 `-71`과 `-68`을 선택하여 `-71`을 남기고 번호가 작은 풍선을 터트리는 기회 한 번을 사용하여 `-71`을 남길 수 있다.

 

이제 문제를 어떻게 풀지 정리해보자.

먼저 `0 ~ i번째까지의 최솟값을 관리하는 dp_before`와 `i ~ len(a)번째 까지의 최솟값을 관리하는 dp_after`을 구한다.

a를 순회하며 현재 풍선인 `cur`의 좌우 풍선들을 모두 터트려 `[before, cur, after]`처럼 세 개의 풍선이 남도록 구한다. `before`와 `after`는 각각 `dp_before`, `dp_after`를 사용하여 O(1) 시간에 구할 수 있다.

`[before, cur, after]` 풍선이 남은 상황에서 `cur`이 `before`, `after` 두 풍선의 수보다 크다면 해당 풍선은 마지막까지 남길 수 없다.

이러한 방식으로 a를 순회하며 answer를 갱신하며 답을 구한다.

 

 

소스코드

---

'''
인접한 풍선 중 번호카 작은 풍선을 남긴다
인접한 풍선 중 번호가 작은 풍선은 1번만 터트릴 수 있음
'''
MAX = 1000000000
def solution(a):
    answer = 0
    dp_before = [0] * len(a)  # dp_before[i]: i번째 이전 리스트의 최솟값
    dp_after = [0] * len(a)  # dp_after[i]: i번째 이후 리스트의 최솟값
    dp_before[0] = a[0]
    for i in range(1, len(a)):
        dp_before[i] = min(dp_before[i - 1], a[i])
    dp_after[-1] = a[-1]
    for i in range(len(a) - 2, -1, -1):
        dp_after[i] = min(dp_after[i + 1], a[i])

    # 맨 처음, 맨 마지막은 항상 가능하므로 빼고 순회
    answer += 2
    for i in range(1, len(a) - 1):
        before = dp_before[i - 1]  # i 이전의 최솟값
        cur = a[i]
        after = dp_after[i + 1]  # i 이후의 최솟값
        if before < cur and after < cur:  # before와 after이 모두 작다면 불가능
            continue
        answer += 1
    return answer