[Codefroce][Python] div.3 #731 - E. Air Conditioners

문제의 핵심은 결국 에어컨으로부터 얼만큼의 거리에 있는가? 입니다.

백준의 최대 직사각형 만들기, SWEA의 수영장 가자 와 동일한 문제로 dp를 이용해 방해물이 없으면 기존값에서 거리값을 늘려가며 기록해주되 방해물(나보다 작은 온도의 에어컨)이 나타나면 그값에서 부터 다시 거리값을 기록해줍니다.

본 풀이는 좌, 우 다른 dp를 사용했으나 경험상 dp하나로도 구현할 수 있습니다.

 

import sys
input = sys.stdin.readline

for test in range(int(input())):
    input()
    n, k = map(int, input().split())
    a = list(map(lambda x: int(x) - 1, input().split()))
    t = list(map(int, input().split()))
    answer = [float('inf')] * n
    for i in range(k):
        answer[a[i]] = t[i]
    dp_right = [0] * n
    dp_left = [0] * n
    last = float('inf')
    for i in range(n):
        last = min(last + 1, answer[i])
        dp_right[i] = last
    for i in range(n-1, -1, -1):
        last = min(last + 1, answer[i])
        dp_left[i] = last
    for i in range(n):
        print(min(dp_left[i],dp_right[i]), end=' ')