99클럽 코테 스터디 25일차 TIL - [프로그래머스/파이썬] - 에어컨

프로그래머스 - 에어컨

풀이

def solution(temperature, t1, t2, a, b, onboard):  
    # 초기값 설정  
    cost = 1000 * 100       # 최댓값 설정(onboard 길이 최댓값 * a,b 최댓값)  
    t1 += 10                # 음수를 제거하기 위해 -10 <= t1, t2 <= 40 을 0 <= t1, t2 <= 50 으로 옮긴다  
    t2 += 10  
    temperature += 10       # t1, t2 도 옮겼으니 temprature 도 + 10 을 해준다  

    # DP[i][j] : i분에 j 온도를 만들 수 있는 가장 적은 전력  
    dp = [[cost] * 51 for _ in range(len(onboard))]  # j = 0 ~ 50  
    dp[0][temperature] = 0  

    flag = 1  # 에어컨을 가동했을때 온도가 변하는 방향, 최적의 온도보다 낮거나 같으면  
    if temperature > t2:  
        flag = -1   # 최적의 온도보다 외부 온도가 높다면  

    for i in range(1, len(onboard)):  
        for j in range(51):  
            ans = [cost]  
            if (onboard[i] == 1 and t1 <= j <= t2) or onboard[i] == 0:  
                # 1. 에어컨을 키지 않고 실외온도와 달라서 실내온도가 -flag 되는 경우  
                if 0 <= j + flag <= 50:  
                    ans.append(dp[i - 1][j + flag])  
                # 2. 에어컨을 키지 않고 현재온도 j 가 실외온도랑 같아서 변하지 않는 경우  
                if j == temperature:  
                    ans.append(dp[i - 1][j])  
                # 3. 에어컨을 키고 현재온도가 변하는 경우  
                if 0 <= j - flag <= 50:  
                    ans.append(dp[i - 1][j - flag] + a)  
                # 4. 에어컨을 키고 현재온도가 희망온도라서 온도가 변하지 않는경우  
                if t1 <= j <= t2:  
                    ans.append(dp[i - 1][j] + b)  

                dp[i][j] = min(ans)  

    answer = min(dp[len(onboard) - 1])  
    return answer

 

def solution(temperature, t1, t2, a, b, onboard):
    # 초기값 설정
    cost = 1000 * 100       # 최댓값 설정(onboard 길이 최댓값 * a,b 최댓값)
    t1 += 10                # 음수를 제거하기 위해 -10 <= t1, t2 <= 40 을 0 <= t1, t2 <= 50 으로 옮긴다
    t2 += 10
    temperature += 10       # t1, t2 도 옮겼으니 temprature 도 + 10 을 해준다

    # DP[i][j] : i분에 j 온도를 만들 수 있는 가장 적은 전력
    dp = [[cost] * 51 for _ in range(len(onboard))]  # j = 0 ~ 50
    dp[0][temperature] = 0

    flag = 1  # 에어컨을 가동했을때 온도가 변하는 방향, 최적의 온도보다 낮거나 같으면
    if temperature > t2:
        flag = -1   # 최적의 온도보다 외부 온도가 높다면

    for i in range(1, len(onboard)):
        # 가지치기 느낌은 나는데 테스트 케이스를 확인해보니 큰 효과는 없는듯?
        start = end = 0

        if onboard[i] :
            start = t1
            end = t2
        else :
            start = min(t1, temperature)
            end = max(t2, temperature)

        for j in range(start, end+1):
            ans = [cost]
            if (onboard[i] == 1 and t1 <= j <= t2) or onboard[i] == 0:
                # 1. 에어컨을 키지 않고 실외온도와 달라서 실내온도가 -flag 되는 경우
                if 0 <= j + flag <= 50:
                    ans.append(dp[i - 1][j + flag]) # 에어컨 off
                # 2. 에어컨을 키지 않고 현재온도 j 가 실외온도랑 같아서 변하지 않는 경우
                if j == temperature:
                    ans.append(dp[i - 1][j])        # 에어컨 off
                # 3. 에어컨을 키고 현재온도가 변하는 경우
                if 0 <= j - flag <= 50:
                    ans.append(dp[i - 1][j - flag] + a) # 에어컨 on
                # 4. 에어컨을 키고 현재온도가 희망온도라서 온도가 변하지 않는경우
                if t1 <= j <= t2:
                    ans.append(dp[i - 1][j] + b)        # 에어컨 on

                dp[i][j] = min(ans)         # 최소 소비 전력 구하기

    answer = min(dp[len(onboard) - 1])      # return
    return answer

현재온도가 변할 수 있는 범위는

min(t1, 실외온도) ~ max(t2, 실외온도)

이 문제 풀이를 위해서 Dynamic Programming 을 활용할 것이다. 2차원 DP 테이블을 활용해서
세로 - 시간, 
가로 - 온도
값 - 최소 소비전력

DP[i][j] = i분 상태의 j도 만들어 낼 수 있는 에어컨의 최소 소비전력

onboard[i]의 값이 1이 되는 경우에는 반드시 실내온도가 t1~t2 안에 위치해야한다는 점이다.
이를 위해서 DP값을 갱신하기 전에, 해당 시간대의 온도 범위를 지정하고 들어가야한다.

답안 2개를 작성했는데 1번 답안과 2번 답안의 차이점은 

for i in range(1, len(onboard)):
        start = 0
        end = 0

        if onboard[i] :
            start = t1
            end = t2
        else :
            start = min(t1, temperature)
            end = max(t2, temperature)

        for j in range(start, end+1):

j열을 51개 다 돌면서 답을 갱신하느냐, start, end 로 정해진 구간만 답안 갱신을 하느냐 차이다. 
실제로 테스트 돌려보니 큰 차이는 없어서 넣어서 돌려도, 51을 다 돌아도 상관없을 듯 하다.

온도 범위에 따라 j-1, j, j+1 에 대해서 답안을 갱신해준다. 갱신 하는 경우는

1. 에어컨을 끄고, 실내온도 방향으로 1도 변경하는 경우
2. 에어컨을 끄고, 온도를 유지하는 경우 (특수한 경우 => 실내온도 == 현재온도)
3. 에어컨을 키고, 온도를 유지하는 경우
4. 에어컨을 키고, 온도를 실내온도와 반대 방향으로 1도 변경하는 경우

이 경우를 생각해서 dp[i][j]를 갱신하면 된다.