2023 현대모비스 알고리즘 경진대회 예선_에어컨

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/214289

파이썬 소스: https://bit.ly/4cFNvDu

 

온도 조건도 범위가 있고, 공조를 하지 않으면 온도가 다시 올라가는 등, 문제를 어떻게 접근해서 풀어야 할지 알기 어려운, 좀 난이도가 있는 문제입니다. 문제에서는 ‘에어컨을 켠다/끈다’고 표현해서, 온도가 감소하는 경우만 생각하게 됩니다. 하지만, 온도 증가/감소 모두 다뤄야 하기 때문에, ‘공조를 한다/안한다’ 라고, 표현하여 문제를 설명하겠습니다.

 하지만, 이 문제에서, 공조를 하느냐? 안하느냐?에 따라서 온도가 1도식 변하게 됩니다.

따라서, 이문제는 동적계획법(Dynamic Programming)로 문제를 풀 수 있습니다.

또 다른 이유로 이 문제가 DP인 이유는, 매분 사람이 탐승하는지 여부도 onboard 변수에서 알려주고 있기 때문에, 분을 column으로 두고, 온도를 row의 인덱스로 사용하는 2차원 배열을 사용해서 문제를 풀 수 있겠구나! 하고 감을 잡을 수 있습니다.

ta, 와 tb를 공조를 하기 전/후의 온도라고 하고, i를 분이라고 가정하면, 아래와 같은 점화식을 만들 수 있습니다.

dp[ta][i], dp[tb][i+1] 의 관계 ta온도에서 tb 온도가 되기 위해서 사용한 에너지 가 dp[tb][i+1]에 저장된다.

 

물론 ta, tb를 컬럼으로 사용할수 도 있지만, 디버깅을 편하게 하기 위해서, 온도가 가로 방향으로 보이도록, 온도를 row 값의 인덱스로 사용하는 것을 추천 드립니다.

 

하지만, 여전히 실내온도의 범위, a, b 그리고, 실외온도 temperature 등의 변수가 있어서, 풀이에 접근하기가 쉽지 않습니다. 게다가, temperature는 a 보다 작은 경우도, b 보다 큰 경우도 있기 때문에, 문제를 풀기에는 아직 단순화할 부분이 있습니다.

 

우선 실내/실외 온도가 -10도까지 있을 수 있기 때문에, 온도를 리스트의 인덱스로 사용할 수 없습니다. 온도를 모두 10도 더해줍니다. 그렇게 되면, 실내/실외 온도 모두 최저 온도가 0으로 되어서, 온도를 배열의 인덱스로 사용할 수 있습니다.

tmpr, t1, t2 = temperature + 10, t1 + 10, t2 + 10

* temperature가 변수이름으로 사용하기 좀 길어서, tmpr로 줄여서 코딩하겠습니다.

온도에 10을 더하더라도, 공조를 하는데 들어가는 소비전력에는 차이가 없습니다. 왜냐면 소비전력은 실내온도를 변화시키거나, 온도를 유지하기 위해서 사용되기 때문에, temperature, t1, t2 모두 에 같은 값을 더하거나 빼더라도, 사용되는 소비전력은 10을 더하기 전과 동일 합니다.

 

온도 변화 delta temperature 를 dt 로 정의 하면, tmpr < t1 인 경우도, t2 < tmpr 인 경우 두가지 경우 모두 가능합니다. 따라서, 공조(온도 변화를 준 경우만)를 했을 때, 온도의 변화를 dt라고 하면, dt는 -1 이거나 +1 일 수 있습니다. 아래와 같이 dt 값을 구할 수 있습니다.

dt = 1 if tmpr < t1 else -1

* dt == 1, tmpr이 낮은 실내온도 보다 낮다면, 공조를 하면, 1도씩 증가합니다.

* dt == -1, tmpr이 높은 실내온도 보다 크다면, 공조를 하면, 1도씩 감소합니다.

 

문제에서 주어진 온도의 범위는 -10~40도 이지만, 리스트의 인덱스로 사용하기 위해서 0~50으로 변환되었습니다. 그렇다면, 우리는 문제를 풀 때, 0~50 범위를 모두 고려해야 하는 것일까요?

온도범위를 고려하는 이유는 문제를 풀기 시작할 때, 실외온도는 tmpr로 정해저있기 때문이고,원하는 온도 범위도 a~b로 정해저 있기 때문입니다. 그러면 우리가 고려해야 하는 온도의 범위가 어디부터 어디까지 일까요?

tmpr < t1 와 tmpr > t2 모두 가능 하기 때문에, tmpr은 우리가 고려해야 할 가장 낮은 온도 이거나, 가장 높은 온도 입니다. 따라서, 아래와 같은 온도 범위를 구할 수 있습니다.

tmpr_lowest = min(tmpr, t1) tmpr_highest = max(tmpr, t2)

 

 매분 지날 때마다, 항상 공조를 하지 않아서 온도가 1도 상승/감소하더라도, 실내온도는 아래 범위를 벗어나지 않습니다.

tmp_lowest <= 실내온도 <= tmpr_highest

 

 온도 범위를 생각해 볼 때, 한가지 더 고려해야 할 부분이 있습니다. onboard[i]가 1인 경우, 사람이 탑승했을 때는, 온도 범위가 t1~t2 로 좁아지게 됩니다. 이제 코드를 보면서 설명해 보겠습니다.

from typing import List def solution(temperature, t1, t2, a, b, onboard):     # 온도를 리스트의 인덱스로 사용하기 위해서는, 온도가 < 0 은 경우가 없어야 한다.     # 10도씨 모두 증가 시켜서, 최저 온도를 0으로 만든다.     # temperature, t1, t2 모두 10도씩 올렸기 때문에 문제의 결과에는 영향이 없다.     tmpr, t1, t2 = temperature + 10, t1 + 10, t2 + 10     # 최대 온도는 50입니다.     TMPR_MAX = 50     # 공조를 해서 온도를 변화시켰을 때, delta temperature, 줄여서 dt 값을 계산합니다.     dt = 1 if tmpr < t1 else -1     # 분을 column으로 온도를 row로, 2차원 배열 dp 리스트를 만들어 줍니다.     dp: List[List] = [[10 ** (2 + 3) for _ in range(len(onboard) + 1)] for _ in range(TMPR_MAX + 1)]     # 여기서 기본값을 채울 때, 10**2 는 a,b 의 최대값 100 에서 왔구요,     # 10**3은 onbaord의 최대길이 1000 에서 왔습니다.     # 소비전력을 최대로 사용한다고 했을 때, 10**5 가 되기 때문에, 초기값을 10 ** (2+3) 으로 잡았습니다.     # 초기값이 최대값이기 때문에, min() 함수를 사용해서 보다 구현을 간단하게 할 수 있습니다. <- 간단하게 구현할 수 있는 이유는 뒤에서 설명하겠습니다.     # dp[ta][i], dp[tb][i+1] 의 관계는     # ta온도에서 tb 온도가 되기 위해서 사용한 에너지 가 dp[tb][i+1]에 저장된다.     # 따라서, len(onboard)길이 보다 1크게 리스트를 만들어야 합니다.     # 문제를 풀기 시작 할 때, dp 배열에 0은 부분은 dp[tmpr][0] 뿐입니다.     # 실외 온도와 실내 온도가 같기 때문에, dp[tmpr][0] 에서부터 온도 변화가 생깁니다.     dp[tmpr][0] = 0     # 사람이 탑승하지 않은 상태에서, 우리가 다뤄야할 온도 범위 입니다.     tmpr_lowest, tmpr_highest, = min(t1, tmpr), max(t2, tmpr)     for i in range(len(onboard)):         # 사람이 탑승하지 않은 상태에서 온도 변화 범위를         # tmpr_min, tmpr_max의 기본값으로 사용합니다.         tmpr_min, tmpr_max = tmpr_lowest, tmpr_highest         if onboard[i]:             tmpr_min, tmpr_max = t1, t2             # 사람이 탑승했다면, 온도 범위는 t1, t2 이내여야 합니다.         for t in range(tmpr_min, tmpr_max + 1):             # 온도가 변하는 공조를 해서, 온도가 1증가/감소 하는 nt가 되는 경우 입니다.             nt = t + dt             if 0 <= nt <= TMPR_MAX:  # dt가 -1/+1 모두 가능하기 때문에, 리스트의 범위를 벗어나는 것을 막아 줍니다.                 dp[nt][i + 1] = min(dp[nt][i + 1], dp[t][i] + a)                 # 온도가 변하는 공조를 했기 때문에, 기존에 사용한 전력(dp[t][i])에 온도 변화 공조에 필요한 소비전력 a를 더해 줍니다.                 # dp의 초기값은 모두 최대 소비전력 (10**5)로 채워저 있기 때문에,                 # 초기값을 가지고 있는 부분은, dp[t][i] + a 값이 되구요,                 # 그 이후부터는 min() 함수의 결과에 따라서, 작은 값을 dp 리스트에 저장합니다.             # 온도가 변하지 않는 공조를 하는 경우 입니다.             if t != tmpr:                 dp[t][i + 1] = min(dp[t][i + 1], dp[t][i] + b)                 # 온도를 유지하는 공조에 필요한 소비전력 +b 가 사용됩니다.             else:  # tmpr과 t온도가 같다면, 소비전력 없이, 현재 온도를 유지 할 수 있습니다.                 dp[t][i + 1] = min(dp[t][i + 1], dp[t][i])             # 마지막으로, 공조를 전혀 하지 않는 경우 입니다.             # dt에 -1를 곱해서, dt 값의 반대 방향으로 온도가 증가/감소합니다.             nt = t + (dt * -1)             if 0 <= nt <= TMPR_MAX:  # dt가 -1/+1 모두 가능하기 때문에, 리스트의 범위를 벗어나는 것을 막아 줍니다.                 dp[nt][i + 1] = min(dp[nt][i + 1], dp[t][i])                 # 이전까지 소비한 소비전력의 합 그대로 min 값에 인자로 넣어줍니다.     answer = 10 ** (2 + 3)     for t in range(tmpr_lowest, tmpr_highest + 1):         # 소비된 전력의 최소값을 찾습니다.         answer = min(answer, dp[t][len(onboard)])     return answer

 

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul