본문 바로가기

카테고리 없음

[프로그래머스] 에어컨 (Python)

def solution(T, T1, T2, a, b, onboard):
    if T<T1:
        T,T1,T2 = -T,-T2,-T1
    N = len(onboard)
    DP = [[1e9]*100 for i in range(N)]; DP[0][T]=0
    for n in range(1,N):
        for t in range(T1,T+1):
            if onboard[n] and not T1<=t<=T2:
                continue
            DP[n][t] = min(DP[n-1][t-1],DP[n-1][t+1]+a,DP[n-1][t]+b)
        if not onboard[n]:
            DP[n][T] = min(DP[n][T],DP[n-1][T])
    return min(DP[-1])

간단한 DP 문제

bottom-up 방식으로 각 시간, 온도별로 드는 최소비용을 시간순으로 기록하면 된다.

 

이때 주의할 점으로는

1. 해당 시간에 사람이 타있는 경우에는 현재 온도가 범위 밖을 벗어나선 안된다.

2. 현재 온도가 외부 온도와 같은 경우에는 이전 온도와 같은 경우도 갱신해주어야한다.

3. 외부 온도가 범위보다 낮은지, 높은지를 고려해주어야한다. 나의 경우에는 외부 온도가 더 낮으면 모든 온도를 음수로 변환하여 통일해주었다.