Python - [백준]14586-도미노(small)

출처

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

문제

최소 갯수의 도미노만 사용하여 모두 넘어뜨리는 문제이다.

접근 방법

이 문제는 어떤 도미노를 건드려야 많이 무너뜨릴 수 있는지 찾는 문제이다.
각각의 도미노 블록에 대해 실행 할 때 마다 몇개가 무너지는지 구하면 오래걸리기 때문에 DP방식으로 메모이제이션 해주어 푼다.

풀이

우선 입력을 받아온 도미노를 정렬해준다.
그 뒤 블록의 index별로 왼쪽 오른쪽으로 각각 넘어뜨렸을때 마지막으로 넘어지는 블록의 인덱스를 저장한 배열을 두개 선언하여 구해준다.

그 뒤 최종 결과가 있는 dp배열을 선언하여 첫번째부터 끝까지 각각 왼쪽부터 현재 i 까지의 최소 횟수를 업데이트 해주고, 그 뒤 오른쪽을 또 검사한다.

i보다 앞서있는 j번째 도미노를 오른쪽으로 넘어뜨렸을 때,i가 같이 넘어진다면 최솟값은 dp[i] = min(dp[i], dp[j - 1] + 1)로 볼 수 있다.
이는 앞서 i보다 왼쪽에 있는 도미노들의 dp가 모두 업데이트 되었기 때문이다.

이 과정을 거쳐 마지막 dp배열을 프린트 하면 끝이다.

코드

import sys
input = sys.stdin.readline
INF = sys.maxsize
def solution(n, arr):
    sol_left = [i for i in range(n)]
    sol_right = [i for i in range(n)]
    for i in range(n):
        left = arr[i][0] - arr[i][1]
        right = arr[i][0] + arr[i][1]
        for j in range(i, -1, -1):
            if left <= arr[j][0]:
                left = min(left, arr[j][0] - arr[j][1])
                sol_left[i] = min(sol_left[i], j)
        for j in range(i + 1, n):
            if right >= arr[j][0]:
                right = max(right, arr[j][0] + arr[j][1])
                sol_right[i] = max(sol_right[i], j)
    dp = [INF for i in range(n)]
    dp[0] = 1
    for i in range(n):
        if sol_left[i] - 1 < 0:
            dp[i] = min(dp[i], 1)
        else:
            dp[i] = min(dp[i], dp[sol_left[i] - 1] + 1)
        for j in range(i):
            if sol_right[j] >= i:
                if j == 0:
                    dp[i] = min(dp[i], 1)
                else:
                    dp[i] = min(dp[i], dp[j - 1] + 1)
    return dp[n - 1]
    
    
    
n = int(input())
arr = [tuple(map(int, input().split())) for _ in range(n)]
arr.sort()
print(solution(n, arr))