[Python] 에어컨

728x90

[level 3] 에어컨 - 214289

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

프로그래머스

SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

💻 문제 정의

외부 온도 temperature가 주어지고, 열차 내 희망 온도가 t1 ~ t2이다. 열차 내부에 에어컨을 가동하면 희망하는 온도 방향으로 온도가 오르거나 내리고, 에어컨을 가동하지 않으면 외부 온도와 가까워지는 방향으로 온도가 오르거나 내린다. 온도는 1분 단위로 1도씩 오르거나 내린다.

해당 열차에 승객이 탑승 했다 안했다가 분 단위로 주어진다. 우리는 승객이 열차에 탑승 하였을 때 실내 온도가 희망 온도에 맞춰질 수 있도록 에어컨을 가동한다고 하였을 때, 전력을 최소로 소모하면서 열차 내 온도를 희망 온도로 유지하고 싶다.

승객이 탑승중인 시간 동안 쾌적한 실내 온도를 유지하기 위한 최소 소비전력을 반환하는 함수를 작성하는 문제이다.

💡 접근 및 설계

다이나믹 프로그래밍 기법으로 설계 하였다. 2차원 DP를 통해 i분 일때 j 온도가 되기 위한 전력을 최소화 하는 방향으로 DP를 설계할 수 있다.

✏️ 알고리즘 풀이

# -10 ~ 40 -> 0 ~ 50으로 치환
OFFSET = 10
MAX_TEMP = 50
INF = 100_000_000

t1 += OFFSET
t2 += OFFSET
outside = temperature + OFFSET

온도의 범위가 -10 ~ 40이다. 이를 0 ~ 50의 값으로 치환해준다. 그에 맞게 다른 값들도 10씩 더해준다.

time = len(onboard)
    
# dp[i][j] = i분일때 j의 온도가 되기 위한 최소 전력
dp = [[INF] * (MAX_TEMP+1) for _ in range(time)]
dp[0][outside] = 0

for i in range(time-1):
    for curr_temp in range(MAX_TEMP + 1):
        if dp[i][curr_temp] == INF:
            continue
            
        curr_cost = dp[i][curr_temp]
        
        # 에어컨 off
        if curr_temp < outside:
            next_temp = curr_temp + 1
        elif curr_temp > outside:
            next_temp = curr_temp - 1
        else:
            next_temp = curr_temp
            
        if 0 <= next_temp <= MAX_TEMP:
            # 손님이 있는 경우 온도 제한
            if onboard[i+1] == 0 or (t1 <= next_temp <= t2):
                dp[i+1][next_temp] = min(dp[i+1][next_temp], curr_cost)
                
        # 에어컨 on (온도 유지)
        next_temp = curr_temp
        if onboard[i+1] == 0 or (t1 <= next_temp <= t2):
            dp[i+1][next_temp] = min(dp[i+1][next_temp], curr_cost+b)
        
        # 에어컨 on (1도 하강)
        if curr_temp - 1 > 0:
            next_temp = curr_temp - 1
            if onboard[i+1] == 0 or (t1 <= next_temp <= t2):
                dp[i+1][next_temp] = min(dp[i+1][next_temp], curr_cost+a)
            
        # 에어컨 on (1도 상승)
        if curr_temp + 1 < MAX_TEMP:
            next_temp = curr_temp + 1
            if onboard[i+1] == 0 or (t1 <= next_temp <= t2):
                dp[i+1][next_temp] = min(dp[i+1][next_temp], curr_cost+a)

DP 테이블은 다음과 같이 설계되어 있다.

먼저 초기 0분대에 실내 온도는 바깥의 온도와 동일하다. 그리고 그때의 소비 전력은 dp[0][outside] = 0이다.

여기서 1분 후로 넘어가기 위해선 에어컨의 작동 유무에 따라 나뉘게 될 것이다.

만약 에어컨이 작동 중이지 않다면, 1분 후의 온도는 바깥의 온도(outside)에 따라 경우가 나뉘게 될 것이다. 바깥의 온도가 낮다면 1분 후의 온도는 1도 낮아질 것이고, 바깥의 온도가 높다면 1분 후의 온도는 높아지고, 같다면 변화 없을 것이다. 이후 바뀐 온도가 희망 온도 범위 내 존재한다면 그때의 전력을 최솟값으로 업데이트 한다.

에어컨이 작동 중이라면, 현재의 온도를 유지할 지, 희망 온도 방향으로 변화시킬지 선택해야 한다. 현재 온도에서 다음 온도로 변할 때 발생하는 전력을 업데이트 한다.

last_guest = 0
for i in range(time-1, -1, -1):
    if onboard[i] == 1:
        last_guest = i
        break
        
answer = min(dp[last_guest][t1:t2+1])

return answer

마지막에 탑승한 승객이 탑승한 시각을 구한다. 그 시간 이후로 에어컨은 OFF일 테니 생각할 필요 없을것이다. 해당 시각에서 t1 ~ t2의 범위 중 가장 작은 값이 최소 소비전력이 된다.

🗒️ 최종 제출 코드

def solution(temperature, t1, t2, a, b, onboard):
    # -10 ~ 40 -> 0 ~ 50으로 치환
    OFFSET = 10
    MAX_TEMP = 50
    INF = 100_000_000
    
    t1 += OFFSET
    t2 += OFFSET
    outside = temperature + OFFSET
    
    time = len(onboard)
    
    # dp[i][j] = i분일때 j의 온도가 되기 위한 최소 전력
    dp = [[INF] * (MAX_TEMP+1) for _ in range(time)]
    dp[0][outside] = 0

    for i in range(time-1):
        for curr_temp in range(MAX_TEMP + 1):
            if dp[i][curr_temp] == INF:
                continue
                
            curr_cost = dp[i][curr_temp]
            
            # 에어컨 off
            if curr_temp < outside:
                next_temp = curr_temp + 1
            elif curr_temp > outside:
                next_temp = curr_temp - 1
            else:
                next_temp = curr_temp
                
            if 0 <= next_temp <= MAX_TEMP:
                # 손님이 있는 경우 온도 제한
                if onboard[i+1] == 0 or (t1 <= next_temp <= t2):
                    dp[i+1][next_temp] = min(dp[i+1][next_temp], curr_cost)
                    
            # 에어컨 on (온도 유지)
            next_temp = curr_temp
            if onboard[i+1] == 0 or (t1 <= next_temp <= t2):
                dp[i+1][next_temp] = min(dp[i+1][next_temp], curr_cost+b)
            
            # 에어컨 on (1도 하강)
            if curr_temp - 1 > 0:
                next_temp = curr_temp - 1
                if onboard[i+1] == 0 or (t1 <= next_temp <= t2):
                    dp[i+1][next_temp] = min(dp[i+1][next_temp], curr_cost+a)
                
            # 에어컨 on (1도 상승)
            if curr_temp + 1 < MAX_TEMP:
                next_temp = curr_temp + 1
                if onboard[i+1] == 0 or (t1 <= next_temp <= t2):
                    dp[i+1][next_temp] = min(dp[i+1][next_temp], curr_cost+a)
            
    last_guest = 0
    for i in range(time-1, -1, -1):
        if onboard[i] == 1:
            last_guest = i
            break
            
    answer = min(dp[last_guest][t1:t2+1])
    
    return answer

💭 오늘의 회고