문제 요약
자동차 실내온도를 제어하는 에어컨 시스템이 있다.
현재 0분의 실내온도는 실외온도와 같다.
승객이 탑승 중인 시간에는 실내온도가 항상 쾌적 범위인 t1 ~ t2 사이에 있어야 한다.
에어컨은 켜거나 끌 수 있고, 켜져 있을 때는 희망온도를 설정할 수 있다.
에어컨 동작 규칙은 다음과 같다.
에어컨이 켜져 있는 경우
실내온도와 희망온도가 다르면 1분 뒤 희망온도 방향으로 1도 이동한다.
현재온도 < 희망온도 -> 1도 상승
현재온도 > 희망온도 -> 1도 하강이때 소비 전력은 a다.
실내온도와 희망온도가 같다면 온도는 유지된다.
이때 소비 전력은 b다.
에어컨이 꺼져 있는 경우
실내온도는 실외온도 방향으로 매 분 1도씩 이동한다.
실내온도와 실외온도가 같다면 변하지 않는다.
에어컨이 꺼져 있으면 전력은 소비하지 않는다.
목표는 승객이 탑승 중인 시간에 실내온도를 쾌적 범위로 유지하면서 소비 전력의 최솟값을 구하는 것이다.
핵심 아이디어
이 문제는 시간에 따라 실내온도가 변한다.
따라서 다음과 같은 DP를 생각할 수 있다.
dp[time][temp]의미는 다음과 같다.
time분에 실내온도가 temp일 때의 최소 소비 전력각 분마다 가능한 실내온도에서 다음 분의 실내온도로 이동하는 경우를 모두 확인한다.
이동 방법은 크게 두 가지다.
- 에어컨을 끈다.
- 에어컨을 켠다.
에어컨을 켠 경우는 다시 다음 세 가지로 볼 수 있다.
- 온도를 유지한다.
- 온도를 1도 낮춘다.
- 온도를 1도 높인다.
온도 범위
프로그래머스 원문 제한에서 온도는 보통 -10도부터 40도 범위 안에서 다룰 수 있다.
따라서 DP 배열의 온도 범위를 다음처럼 잡는다.
MIN_TEMP = -10
MAX_TEMP = 40파이썬 리스트 인덱스는 음수를 그대로 쓰기 어렵기 때문에 OFFSET을 더해 저장한다.
OFFSET = 10예를 들어 실제 온도 -10은 인덱스 0이 된다.
-10 + 10 = 0실제 온도 28은 인덱스 38이 된다.
28 + 10 = 38DP 초기값
0분의 실내온도는 항상 실외온도와 같다.
dp[0][temperature + OFFSET] = 0아직 전력을 쓰지 않았으므로 비용은 0이다.
승객 탑승 조건
승객이 탑승하지 않은 시간에는 실내온도가 어떤 값이어도 상관없다.
하지만 승객이 탑승 중인 시간에는 반드시 t1 ~ t2 사이여야 한다.
이를 함수로 만들면 다음과 같다.
def is_comfortable(temp, time):
if onboard[time] == 0:
return True
return t1 <= temp <= t2다음 시간으로 이동할 때, 이동 후 온도가 해당 시간의 조건을 만족하는지 확인해야 한다.
전이 1: 에어컨 끄기
에어컨을 끄면 실내온도는 실외온도 방향으로 1도 이동한다.
if temp < temperature:
next_temp = temp + 1
elif temp > temperature:
next_temp = temp - 1
else:
next_temp = temp에어컨이 꺼져 있으므로 추가 비용은 없다.
next_cost = current_cost전이 2: 에어컨 켜고 온도 유지
에어컨이 켜져 있고 희망온도와 현재 실내온도가 같으면 온도는 유지된다.
next_temp = temp이때 소비 전력은 b다.
next_cost = current_cost + b전이 3: 에어컨 켜고 온도 변경
에어컨이 켜져 있고 희망온도와 현재 실내온도가 다르면 실내온도는 희망온도 방향으로 1도 이동한다.
따라서 다음 온도는 두 가지가 가능하다.
temp - 1
temp + 1이때 소비 전력은 a다.
next_cost = current_cost + a전체 코드
def solution(temperature, t1, t2, a, b, onboard):
MIN_TEMP = -10
MAX_TEMP = 40
OFFSET = 10
INF = 10**15
size = MAX_TEMP - MIN_TEMP + 1
time_count = len(onboard)
dp = [
[INF] * size
for _ in range(time_count)
]
dp[0][temperature + OFFSET] = 0
def is_comfortable(temp, time):
if onboard[time] == 0:
return True
return t1 <= temp <= t2
for time in range(time_count - 1):
for temp_index in range(size):
current_cost = dp[time][temp_index]
if current_cost == INF:
continue
temp = temp_index - OFFSET
# 1. 에어컨을 끄는 경우
if temp < temperature:
next_temp = temp + 1
elif temp > temperature:
next_temp = temp - 1
else:
next_temp = temp
if MIN_TEMP <= next_temp <= MAX_TEMP:
if is_comfortable(next_temp, time + 1):
next_index = next_temp + OFFSET
dp[time + 1][next_index] = min(
dp[time + 1][next_index],
current_cost,
)
# 2. 에어컨을 켜고 현재 온도를 유지하는 경우
next_temp = temp
if is_comfortable(next_temp, time + 1):
next_index = next_temp + OFFSET
dp[time + 1][next_index] = min(
dp[time + 1][next_index],
current_cost + b,
)
# 3. 에어컨을 켜고 온도를 1도 낮추거나 높이는 경우
for next_temp in (temp - 1, temp + 1):
if not (MIN_TEMP <= next_temp <= MAX_TEMP):
continue
if not is_comfortable(next_temp, time + 1):
continue
next_index = next_temp + OFFSET
dp[time + 1][next_index] = min(
dp[time + 1][next_index],
current_cost + a,
)
return min(dp[-1])왜 그리디가 아니라 DP인가?
현재 가장 적은 전력을 쓰는 선택이 나중에도 항상 좋은 선택은 아니다.
예를 들어 당장은 에어컨을 끄는 것이 비용이 0이라 좋아 보일 수 있다.
하지만 나중에 승객이 탑승하는 시점에 쾌적 범위를 맞추기 위해 더 많은 전력을 써야 할 수 있다.
반대로 미리 온도를 조절해두면 이후 전력 사용을 줄일 수 있다.
따라서 각 시간과 온도 상태별 최소 비용을 모두 관리하는 DP가 필요하다.
시간 복잡도
시간의 길이를 T, 온도 범위를 R이라고 하자.
각 시간마다 가능한 온도 상태를 모두 확인한다.
각 상태에서 확인하는 전이는 상수 개수다.
O(T × R)온도 범위는 -10부터 40까지이므로 R = 51이다.
따라서 사실상 O(T)에 가깝다.
공간 복잡도
DP 배열은 시간과 온도 범위만큼 사용한다.
O(T × R)온도 범위가 작기 때문에 충분히 가볍다.
정리
이 문제는 시간에 따라 실내온도가 변하는 상태 전이 문제다.
핵심은 다음과 같다.
dp[time][temp]를 현재 시간과 온도에서의 최소 소비 전력으로 정의한다.- 에어컨을 끄면 실외온도 방향으로 1도 이동한다.
- 에어컨을 켜고 온도를 유지하면 비용
b가 든다. - 에어컨을 켜고 온도를 바꾸면 비용
a가 든다. - 승객이 탑승 중인 시간에는
t1 ~ t2범위만 허용한다.
각 시간마다 가능한 모든 온도를 관리하면 최소 소비 전력을 안정적으로 구할 수 있다.
