둔필승총

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

[문제 정보]

먼저 온도가 여러 개 나오는데 실내온도, 실외온도, 희망온도가 주어지고, 또 승객들 등등 여러 가지 정보가 한번에 나온다. 한번에 읽으면 정리가 안되기 때문에 어떤 걸 해결해야하는지 고민해봐야 한다. 

먼저 온도가 변하는 것을 생각하지 말고 온도가 어떤 범위 내에 있어야 하는지를 생각해보자. 승객이 있을 때는 온도는 t1~t2에 있어야 한다. 그리고 승객이 없을 때는 온도가 어디든지 사실 상관이 없다. 그러나 문제는 온도는 1도씩밖에 바뀌지 않기 때문에 승객이 있기 1분 전에는 반드시 t1-1에 있거나 t2+1에 있어야 승객이 있을 때 범위 내에 있게 된다. 

이번엔 온도가 어떻게 변하는지 살펴보겠다. 일단 에어컨이 꺼져 있을 경우, 온도는 실외온도를 따라간다. 에어컨을 껐는데 실외온도에 차이가 없다면 온도는 그대로 유지가 된다.

에어컨이 켜져 있을 경우엔 2가지 이다. 에어컨을 켜고 온도를 유지하는 경우와 에어컨을 켜서 실내온도와 반대 방향으로 1도 변경하는 경우이다. 

이렇게 단계적으로 생각해보면 희망온도는 사실 의미가 없다. 에어컨을 켜서 온도를 변하게 할 것인지 아니면 유지할 것인지의 문제일 뿐이다.

• 에어컨 X, 실내온도 방향으로 1도 변경하는 경우(비용 0)
• 에어컨 X, 온도를 유지하는 경우(비용 0)
• 에어컨 O, 온도를 유지하는 경우(비용 b)
• 에어컨 O, 온도를 실내온도와 반대 방향으로 1도 변경하는 경우(비용 a)

여기까지 이해하고 문제를 풀면 된다.

[문제 해설]

먼저 시간의 흐름이 있고, 온도의 변화도 있으므로 dp 2차원을 생각해내야 한다. 시간이 흐름에 따라 온도가 어떻게 변화하는지 확인하여 최적의 비용을 계산할 수 있기 때문이다.

DP를 사용하려면 문제가 있다. 지금 온도 범위는 -10도에서 40도까지인데 2차원 배열의 인덱스에는 음수가 들어갈 수 없다는 점이다. 그래서 온도를 임의로 10도씩 올려서 계산한다. 

그리고 dp를 사용하여 int(1e9)의 큰 값으로 모든 값들을 초기화 한다.

처음의 온도는 실외온도와 같다고 하였으므로 dp[0][temperature]은 0으로 초기화해준다. (여기가 출발점이다.)

그 이후에는 dp를 1부터 주어진 onboard의 길이까지 진행하면 된다. 

승객이 있을 경우는 dp 온도를 t1에서 t2만 구하면 된다. 그리고 승객이 없다면 나머지를 굳이 구할 필요없이 min(t1, 실외온도) 에서 max(t2, 실외온도)로 구하면 된다. 실외온도는 t1~t2 바깥 값이므로 이렇게 범위를 구하면 된다. 온도가 계속하여 이 사이의 값에 있어야 효율적임을 알 수 있다. 이유는 예시를 하나 생각해보면 된다. t1이 10도 이고, 실외온도가 8도라고 가정하면 8도 이상이어야 된다. 에어컨을 사용하여 8도 밑으로 내려갈 이유가 없다. (에어컨의 소비전력이 최소화가 되지 않는다)

그래서 먼저 범위를 구해주고 범위내의 dp값을 업데이트하는 식을 통해서 진행하면 된다. 

이 업데이트 하는 식이 조금 고민해야 한다. 

for j in range(start, end + 1):
    if j - 1 < 0:
        x = int(1e9)
    else:
        x = dp[i - 1][j - 1]
    if j + 1 > 50:
        y = int(1e9)
    else:
        y = dp[i - 1][j + 1]
    if j < temperature:
        dp[i][j] = min(x, y + a, dp[i - 1][j] + b)
    elif j > temperature:
        dp[i][j] = min(x + a, y, dp[i - 1][j] + b)
    elif j == temperature:
        dp[i][j] = min(x, y, dp[i - 1][j])

여기서 먼저 j-1이 0보다 작거나 j+1이 50을 넘어가면 계산이 안되므로 해당 값들을 처리해준다. 

먼저 j가 실외온도보다 낮을때 처리하는 경우를 생각해보자. dp[i][j]는 i분에 j온도가 되기 위한 비용이다. 

첫번째 먼저 i-1분에 j-1온도일 때는 실외온도를 따라가므로 에어컨이 없더라도 1도 올라간다. 

두번째 i-1분에 j+1온도일 때는 실외온도를 따라가면 j+2가 되거나 j+1이 유지(실외온도가 j+1이라면)되므로 j가 되기 위해서는 에어컨을 틀어서 온도를 낮춰야 한다. 

세번째 i-1분에 j온도일때는 유지만 하면 된다. 만약 에어컨을 끄면 실외온도를 따라가서 온도가 올라가므로 유지하려면 에어컨을 켜서 유지해야 한다. 에어컨이 유지하는 비용은 b라고 명시해주었다. 따라서 식은 다음과 같다. 여기서 x는 dp[i-1][j-1], y는 dp[i-1][j+1]이라고 생각하면 된다.

if j < temperature:
    dp[i][j] = min(x, y + a, dp[i - 1][j] + b)

그 다음에는 j가 실외온도보다 높을때 살펴보겠다. 

먼저 현재온도가 j-1이라면 j가 되려면 에어컨을 켜야한다. 아니면 실외온도를 따라가므로 온도가 떨어지거나 유지되기 때문이다.

두번째 j+1온도라면 실외온도를 그냥 따라가면 내려가므로 에어컨을 꺼도 된다.

세번째 j온도라면 유지를 해야한다. 그럼 그냥 b 비용을 내면된다. 이 세 개중에서 최소가 dp[i][j]가 된다.

elif j > temperature:
    dp[i][j] = min(x + a, y, dp[i - 1][j] + b)

마지막으로 j와 실외온도가 같을때 이다.

첫번째 현재온도가 j-1이라면 실외온도를 따라 올라가면 되므로 에어컨이 필요없다.

두번째 현재온도가 j+1이라면 실외온도를 따라 내려가면 되므로 에어컨이 필요없다.

세번쨰 현재온도가 j라면 실외온도 현재온도 목표온도가 다 같으므로 그냥 나두면 된다.

elif j == temperature:
    dp[i][j] = min(x, y, dp[i - 1][j])

이렇게 점화식을 계산하고 마지막 dp[i][j]에서 i가 onboard의 마지막일때 가능한 비용들이 나온다. 이 중 최소값이 정답이 되게 된다.

[코드]

def solution(temperature, t1, t2, a, b, onboard):
    temperature = temperature + 10
    t1 = t1 + 10
    t2 = t2 + 10

    dp = [[int(1e9)] * 51 for _ in range(len(onboard))]
    dp[0][temperature] = 0
    for i in range(1, len(onboard)):
        if onboard[i] == 1:
            start = t1
            end = t2
        else:
            start = min(t1, temperature)
            end = max(t2, temperature)
        for j in range(start, end + 1):
            if j - 1 < 0:
                x = int(1e9)
            else:
                x = dp[i - 1][j - 1]
            if j + 1 > 50:
                y = int(1e9)
            else:
                y = dp[i - 1][j + 1]
            if j < temperature:
                dp[i][j] = min(x, y + a, dp[i - 1][j] + b)
            elif j > temperature:
                dp[i][j] = min(x + a, y, dp[i - 1][j] + b)
            elif j == temperature:
                dp[i][j] = min(x, y, dp[i - 1][j])
        if i == len(onboard) - 1:
            return min(dp[len(onboard) - 1])

[후기]

실제 현대모비스 알고리즘 대회 때 머리만 싸매다가 못풀었었는데.. 다시 풀어도 머리가 터질 뻔했었다.
어려운 알고리즘이 있는 것보다 더 어려운 문제가 아닐까..(dp만 알면 풀 수는 있는)
그래도 좋은 문제 같아서 나중에 코딩 테스트 전에 한번 풀어보면 또 좋을것 같다.