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

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

프로그래머스

 

Status : Solved

 

Time : 00:25:37

 

---

 

문제 설명

 

 

현대모비스에서 개발한 실내공조 제어 시스템은 차내에 승객이 탑승 중일 때 항상 쾌적한 실내온도(t1 ~ t21)를 유지할 수 있도록 합니다. 현재(0분) 실내온도는 실외온도와 같습니다.

실내공조 제어 시스템은 실내온도를 조절하기 위해 에어컨의 전원을 켜 희망온도를 설정합니다. 희망온도는 에어컨의 전원이 켜져 있는 동안 원하는 값으로 변경할 수 있습니다. 실내온도와 희망온도가 다르다면 1분 뒤 실내온도가 희망온도와 같아지는 방향으로 1도 상승 또는 하강합니다. 실내온도가 희망온도와 같다면 에어컨이 켜져 있는 동안은 실내온도가 변하지 않습니다.

에어컨의 전원을 끄면 실내온도가 실외온도와 같아지는 방향으로 매 분 1도 상승 또는 하강합니다. 실내온도와 실외온도가 같다면 실내온도는 변하지 않습니다.

에어컨의 소비전력은 현재 실내온도에 따라 달라집니다. 에어컨의 희망온도와 실내온도가 다르다면 매 분 전력을 a만큼 소비하고, 희망온도와 실내온도가 같다면 매 분 전력을 b만큼 소비합니다. 에어컨이 꺼져 있다면 전력을 소비하지 않으며, 에어컨을 켜고 끄는데 필요한 시간과 전력은 0이라고 가정합니다.

실내공조 제어 시스템은 차내에 승객이 탑승 중일 때 실내온도를 t1 ~ t2도 사이로 유지하면서, 에어컨의 소비전력을 최소화합니다.

 

* 예시는 문제 링크를 참조해 주세요

 

실외온도를 나타내는 정수 temperature, 쾌적한 실내온도의 범위를 나타내는 정수 t1, t2, 에어컨의 소비전력을 나타내는 정수 a, b와 승객이 탑승 중인 시간을 나타내는 1차원 정수 배열 onboard가 매개변수로 주어집니다. 승객이 탑승 중인 시간에 쾌적한 실내온도를 유지하기 위한 최소 소비전력을 return 하도록 solution 함수를 완성해 주세요.

 

 

입력 및 출력

 

제한사항

• -10 ≤ temperature ≤ 40
• -10 ≤ t1 < t2 ≤ 40
  • temperature는 t1 ~ t2 범위 밖의 값입니다.
• 1 ≤ a, b ≤ 100
  • a는 에어컨의 희망온도와 실내온도가 다를 때의 1분당 소비전력을 나타냅니다.
  • b는 에어컨의 희망온도와 실내온도가 같을 때의 1분당 소비전력을 나타냅니다.
• 2 ≤ onboard의 길이 ≤ 1,000
  • onboard[i]는 0 혹은 1이며, onboard[i]가 1이라면 i분에 승객이 탑승 중이라는 것을 의미합니다.
  • onboard[0] = 0
  • onboard에 1이 최소 한 번 이상 등장합니다.
• 승객이 탑승 중인 시간에 쾌적한 실내온도를 유지하는 것이 불가능한 경우는 주어지지 않습니다.

 

입출력 예

 

temperature	t1	t2	a	b	onboard	result
28	18	26	10	8	[0, 0, 1, 1, 1, 1, 1]	40
-10	-5	5	5	1	[0, 0, 0, 0, 0, 1, 0]	25
11	8	10	10	1	[0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1]	20
11	>8	10	0	100	[0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1]	60

 

 

---

 

풀이

 

국어 문제 시즌 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])

풀이 완료!