이 문제에 대해 감이 전혀 안잡힌다면, 해설을 보고 다시 도전 해보세요!

해당 문제의 유형은 Dynamic Programming 유형입니다.
이는, 따로 임시 저장 공간을 할당하여, 전에 계산했던, 값을 다시 재사용하여
중복되는 계산을 줄이기 위해 사용됩니다.

보통 DP는 재귀적인 호출로 구현하는 Top-Down방식과,
낮은 문제의 답을 쉽게 구할 수 있을 때, 순차적으로 for문으로 구현하는 Bottom-Up 방식으로 갈리게 됩니다.

Top-Down은 상위 개념에서 한 번에 점화식을 찾아낼 수 있고, 이 점화식이 한 또다른 점화식을 도출해낼 수 있을 때
구현하면, 사용하기 좋습니다.

Bottom-Up은 낮은 문제부터 빌드업해 나가는 방식으로,
낮은 문제의 정답을 확실히 구할 수 있는 경우에 사용하면 좋은 방식입니다.

그럼, 이 문제는 어떤 방식으로 풀어야 할까요?

뭐 사실은, DP문제라면, 두 가지 방식다 풀이가 가능할 것으로 보이지만?
해당 문제는 바텀업 방식으로 푸는 것이 좀 더 직관적인 풀이가 가능합니다.

이제부터 그 풀이에 대해 알아봅시다.

먼저, 해당 문제가 좀 복잡하게 얽혀있지만, 그 중에서 문제를 풀기 위한
최소 조건을 문제에서 추출해낼 수 있어야 합니다.

해당 문제는 4가지의 경우로 나타낼 수 있습니다.

• 에어컨을 끄고, 실내온도 방향으로 1도 변경하는 경우

• 에어컨을 끄고, 온도를 유지하는 경우 (특수한 경우 => 실내온도 == 현재온도)

• 에어컨을 키고, 온도를 유지하는 경우

• 에어컨을 키고, 온도를 실내온도와 반대 방향으로 1도 변경하는 경우

이렇게 4가지의 경우를 찾아낼 수 있어야 합니다.
또한, 문제의 잘 읽어보면, 희망온도는 사실상 아무런 역할도 하지 못한다는 사실을 눈치채야합니다.
희망온도를 가지고 연연하였다면, 이 문제의 난이도를 올리게 될 뿐이랍니당

그럼, 이 4가지의 조건을 어떻게 계산해야할까요?

그러기 위해서는 또 하나의 계산과정이 필요합니다.
바로, 실내온도가 변할 수 있는 범위를 구해야합니다.
이게 무슨 소리냐구요?

문제를 잘읽어보시면, 승객이 있는 동안에만, t1~t2 의 온도를 유지만 하면 됩니다.
이걸 잘 생각해보면, t1~t2의 온도를 넘어가는 행위는 상당히 비효율적인 일이 됩니다.
여기까지 눈치채셨다면, 당신은 아주 똑똑합니당

근데, 사실 범위는 또 존재합니다. 바로, 실외온도라는 변수가 있기 때문인데요.
에어컨이 off상태일 경우에는, 실내온도 실외온도와 가까워지는 방향으로 이동하려고 하기에
이를 이용하여 효율적인 냉방 시스템을 구현할 수 있습니다.

그래서 사실 현재온도가 변할 수 있는 범위는

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

와 같이 됩니다. 실외온도가 큰지 작은지 알 수 없기에, 이렇게 표현 할 수 있겠습니다.
가장 이상적인 상태는, 실외온도가 t1~t2 범위에 들어가는 상태라는걸 눈치채면 당신은 눈치백단!
실외온도가 t1~t2사이에 존재하면, 에어컨이 가동할필요가 없으므로, 답이 0이 되겠죠!
( + temparature는 아쉽게도 t1~t2 범위 밖이다 ㅠㅠ)

자 그러면, 우리는 또 무엇을 고려해야할까요?
온도의 범위가 -10~40도 라는 것을 감안해야합니다.
실제로 우리가 DP배열을 만들게 된다고 하면, -10~40도를 표현할 수 없습니다.

그래서, 우리는 이를 간단하게 조치할 수 있는 방법이 있습니다.
바로, 그냥 10도 올려버리는 겁니닷
효율적인지는 모르겠으나, 그냥 이 방법이 가장 쉽습니다.
실외온도, t1, t2의 값을 전부 10도씩 올려버리면, 음수 온도는 고려하지 않아도 됩니다.

그럼 이제 DP배열을 만들어볼건데,
이차원 DP로 만들겁니다.

세로축은, 시간축이 되고,
가로축은, 온도축이 되고,
저장할 값은 최소 소비전력이 됩니다.

즉,

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

이렇게 표현이 가능합니다.
그럼 대충 감이 오겠죠?

그런데, DP를 연산하기전에 귀찮게도 고려해야 할 것이 하나 더 있습니다.
onboard[i]의 값이 1이 되는 경우에는 반드시 실내온도가, t1~t2 안에 위치해야한다는 점입니다.
이를 위해서, 우리는 DP의 값을 갱신하기 전에, 해당 시간대의 온도 범위를 지정하고 들어가야 합니다.

for i in range(1, N): #0분일 때의 소비전력은 실외온도에 한해서 0일거임.
    start = 0
    end = 0
    if onboard[i]:
        start = t1
        end = t2
    else:
        start = 최소온도
        end = 최대온도

    for j in range(start, end + 1):
        이어서 로직 수행

최소온도와 최대온도는 우리가 아까 고려해야될 효율적인 온도 범위를 계산한 값이었습니다.
그렇지만, onboard[i]가 1인 경우에는 해당 온도 사이의 값에만 도달할 수 있는 데이터만 기록해야합니다.
그래서, 두 번째 for문을 돌리기 전에, 업데이트 할 온도의 범위를 제한합니다.
그렇게 되면, 자연스럽게, 승객이 탑승한 경우에는 온도가 유지되는 범위에서 소비 전력을 기록할 수 있게됩니다.

그런데, 그 다음이 가장 중요합니다.
DP의 값은 어떻게 갱신할 수 있을까요?

먼저, 현재 섭씨 j도 에 도달하기 위해서는 이전의 온도가 몇 도여야 할까요?

답은 간단합니다.

j- 1, j, j+ 1

해당 온도만이 현재 j도를 만들어 낼 수 있게됩니다.
왜냐하면, 문제에서 실내온도는 분당 반드시 1도씩만 차이날 수 밖에 없다고 명시했기 때문입니다.

그렇게 된다면, 현재 temp를 만들기 위해서는

dp[i-1][j-1] 으로 부터 dp[i][j]로 오는 경우
dp[i-1][j]로 부터 dp[i][j]로 오는 경우
dp[i-1][j+1]로 부터 dp[i][j]로 오는 경우

해당 경우를 살펴봐야합니다.
여기에, 해당 온도에서, 현재온도로 이동하는 과정이 가장 효율적인 선택지를 부여하면 됩니다.

현재 도달해야하는 온도 j도가, 실외기온보다 높은 상태에서, j - 1도를 j도로 맞춰주기 위해서는,
에어컨을 가동하여, 온도를 높이는 방법이 최선입니다. 즉, 변동 비용 a가 소요됩니다.

현재 도달해야하는 온도 j도가, 실외기온보다 낮은 상태에서, j - 1 도를 j도로 맞춰주기 위해서는
에어컨을 off하여, 온도가 자연적으로 j로 이동하게 만드는 방법 최선입니다, 이 경우에는 0이 소요됩니다.

현재 도달해야하는 온도 j도가, 실외기온보다 낮은 상태에서, j + 1도를 j도로 맞춰주기 위해서는,
에어컨을 가동하여, 온도를 낮추는 방법이 최선입니다. 즉, 변동 비용 a가 소요됩니다.

현재 도달해야하는 온도 j도가, 실외기온보다 높은 상태에서, j + 1 도를 j도로 맞춰주기 위해서는
에어컨을 off하여, 온도가 자연적으로 j로 이동하게 만드는 방법 최선입니다, 이 경우에는 0이 소요됩니다.

전 타임과 같은 온도를 유지하는 경우는, j도가 실외기온과 같다면, 비용은 0이고,
같지 않다면, 유지비용 b가 소요됩니다.

이 값들을 모두 계산하여, 가장 작은 값을 dp[i][j]에 갱신하게 만들면 됩니다.

이렇게 모든 경우를 계산하고 나면은
dp배열을 가장 마지막 시간축의 요소중에서 가장 작은 값이 답이 됩니다.

min(dp[len(onboard)-1])

이렇게 답을 제출하면, 문제를 풀 수 있게 됩니다.

이 문제가 언뜻보면, Greedy 유형과도 같아 보이지만,
해당 전략을 짜는 것은, 그렇게 쉽지만은 않아 보입니다.

특히, 현실세계의 동작 방식은 Greedy로 전략을 구성하여 효율적이게 만드는 것이 자연스럽지만,
문제에서는 승객이 탑승할 정보를 미리 예측하여 알려주었으므로,
이를 이용하여 풀어야합니다.
Greedy로 단 시간의 소비 전력을 계산하여 효율적인 가동을 구현할 수는 있겠지만,
탑승할 승객의 시기를 예측하여, 온도를 조절하는 것은 쉽지 않아보입니다.

만약, 이 문제를 Greedy유형으로 푸셨다면, 정말 대단한 분이라고 말씀드리고 싶습니다.
Greedy는 항상 최적해를 보장하지 못하기에, 이런 유형의 문제에는 선호되지 않기 때문입니다.
고려해야 할 조건이 수두룩하기 때문이죠.

특히, 해당 문제는 시간이 최대 1000분, 온도의 범위차가 최대 50도 이므로
DP배열 1000 * 50 만큼의 공간만 있으면 되기에, 완전 탐색이 충분히 가능합니다.

해당 해설이 도움이 되었길 바라며, 20000 하겠습니다.
빠잉