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

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

프로그래머스

 

Status : Solved

 

Time : 00:25:37

 

---

 

문제 설명

자세한 문제 및 예시는 링크를 참조해 주세요!

입력 및 출력

 

입출력 예시는 링크를 참조해 주세요!

 

---

 

풀이

 

국어 문제 시즌 2. 이 지문 속에서 핵심을 찾아내는 것이 포인트이다.

 

우선, 이 문제는 얼핏 보면 그리디 문제처럼 보일 수 있다. 하지만 온도값의 범위는 최대 50, 시간 길이는 최대 1000이므로 1000 * 50의 최대 연산 단위 동안 모든 경우의 수(에어컨의 가동여부, 온도의 변화여부)를 검증하여 부분 최적해를 계산해 볼 수 있다. 따라서 2차원 DP 기법을 사용해야 한다.

 

특히 함정으로 주의해야 할 점은 '희망온도'의 존재이다. 얼핏 보면 1. 에어컨 가동 여부 및 2. 가동시 최적의 희망온도를 찾아내는 문제처럼 보이지만, 본 문제에서는 거기까지를 요구하지 않는다(즉 요구하는 경우 이 문제의 난이도는 더 상승하게 된다.). 앞서 말했듯 이 문제는 그리디의 탈을 쓴 DP이다. 사실상 에어컨을 틀 때, 희망온도는 에어컨 온도를 높이거나, 낮추거나, 유지하는 세 기능을 위한 요건 중 하나일 뿐이다(희망온도와 현재온도 차가 얼마나 나던 간에 비용은 변하지 않는다!)

 

즉 현재 시점이 i, 그리고 현재 온도가 j 인 최소 비용을 dp[i][j]라고 두면...

• 에어컨을 끌 경우 : 다음 온도 t는 실외온도와 더 가까워진다. (j+1, j-1, j 중 하나가 된다) 즉 dp[i+1][t] = min(dp[i+1][t], dp[i][j])로 업데이트 가능하다.
• 에어컨을 켤 경우 : 다음 온도 t는 세 가지 경우가 존재할 수 있다. (j+1, j-1, j) 그리고 이에 맞추어 소비전력 c도 변화한다. (a, a, b) 즉 dp[i+1][t] = min(dp[i+1][t], dp[i][j] + c)로 업데이트 가능하다.
• 그리고, 다음 상태가 onboard일때 주어진 범위 t1 <= t <= t2를 만족시키는 제약 조건이 포함되어 있다. 즉 이 제약조건을 지키지 못한다면, 업데이트가 수행되어서는 안 된다.

 

연산이 끝난 후, 마지막 시점 dp[-1]의 최솟값을 반환하면 된다.

 

풀이 코드

MAX = float('inf')

def solution(temperature, t1, t2, a, b, onboard):
    temperature += 10
    t1 += 10
    t2 += 10
    length = len(onboard)
    temp_dp = [[MAX]*51 for _ in range(length)]
    temp_dp[0][temperature] = 0
    
    def check(idx, temp) :
        return not (onboard[idx] and not t1 <= temp <= t2)
    
    for i in range(length-1) :
        for j in range(51) :
            if temp_dp[i][j] == MAX :
                continue
                
            # off case :
            if j < temperature :
                temp = j+1
            elif j > temperature :
                temp = j-1
            else :
                temp = j
                
            if check(i+1, temp) :
                temp_dp[i+1][temp] = min(temp_dp[i+1][temp], temp_dp[i][j])
                
            # on case :
            for temp, cost in [(j+1, a), (j-1, a), (j, b)] :
                if not check(i+1, temp) or not -1 < temp < 51 :
                    continue    
                temp_dp[i+1][temp] = min(temp_dp[i+1][temp], temp_dp[i][j] + cost)
    
    return min(temp_dp[-1])

풀이 완료!