[프로그래머스] 에어컨(2023 현대모비스 알고리즘 경진대회 예선)

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

프로그래머스

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

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Level 3

 

문제

현대모비스에서 개발한 실내공조 제어 시스템은 차내에 승객이 탑승 중일 때 항상 쾌적한 실내온도(t1 ~ t2)를 유지할 수 있도록 합니다. 현재(0분) 실내온도는 실외온도와 같습니다.

실내공조 제어 시스템은 실내온도를 조절하기 위해 에어컨의 전원을 켜 희망온도를 설정합니다. 희망온도는 에어컨의 전원이 켜져 있는 동안 원하는 값으로 변경할 수 있습니다. 실내온도와 희망온도가 다르다면 1분 뒤 실내온도가 희망온도와 같아지는 방향으로 1도 상승 또는 하강합니다. 실내온도가 희망온도와 같다면 에어컨이 켜져 있는 동안은 실내온도가 변하지 않습니다.

에어컨의 전원을 끄면 실내온도가 실외온도와 같아지는 방향으로 매 분 1도 상승 또는 하강합니다. 실내온도와 실외온도가 같다면 실내온도는 변하지 않습니다.

에어컨의 소비전력은 현재 실내온도에 따라 달라집니다. 에어컨의 희망온도와 실내온도가 다르다면 매 분 전력을 a만큼 소비하고, 희망온도와 실내온도가 같다면 매 분 전력을 b만큼 소비합니다. 에어컨이 꺼져 있다면 전력을 소비하지 않으며, 에어컨을 켜고 끄는데 필요한 시간과 전력은 0이라고 가정합니다.

실내공조 제어 시스템은 차내에 승객이 탑승 중일 때 실내온도를 t1 ~ t2도 사이로 유지하면서, 에어컨의 소비전력을 최소화합니다.

다음은 실외온도가 28도, t1= 18, t2 = 26, a = 10 b = 8인 예시입니다.

시간(분)승객 탑승

0	x
1	x
2	o
3	o
4	o
5	o
6	o

• 승객이 탑승 중인 2 ~ 6분의 실내온도를 18 ~ 26도 사이로 유지해야 합니다.

다음은 2 ~ 6분의 실내온도를 쾌적한 온도로 유지하는 방법 중 하나입니다.

시간(분)승객 탑승실내온도희망온도

0	x	28	26
1	x	27	26
2	o	26	26
3	o	26	26
4	o	26	26
5	o	26	26
6	o	26	off

• 0분의 실내온도는 항상 실외온도와 같습니다.
• 6분에 에어컨의 전원을 껐습니다.

0 ~ 5분에 에어컨의 희망온도를 26도로 설정했습니다. 0 ~ 1분에 희망온도와 실내온도가 다르므로 전력을 매 분 10씩, 2 ~ 5분에 희망온도와 실내온도가 같으므로 전력을 매 분 8씩 소비했습니다. 이때 총 소비전력은 52(= 2 × 10 + 4 × 8)입니다.

다음은 2 ~ 6분의 실내온도를 쾌적한 온도로 유지하는 또 다른 방법입니다.

시간(분)승객 탑승실내온도희망온도

0	x	28	24
1	x	27	24
2	o	26	24
3	o	25	24
4	o	24	off
5	o	25	off
6	o	26	off

0 ~ 3분에 에어컨의 희망온도를 24도로 설정해 전력을 매 분 10씩 소비했습니다. 이때 총 소비전력은 40(= 4 × 10)이며, 이보다 소비전력이 적어지는 방법은 없습니다.

실외온도를 나타내는 정수 temperature, 쾌적한 실내온도의 범위를 나타내는 정수 t1, t2, 에어컨의 소비전력을 나타내는 정수 a, b와 승객이 탑승 중인 시간을 나타내는 1차원 정수 배열 onboard가 매개변수로 주어집니다. 승객이 탑승 중인 시간에 쾌적한 실내온도를 유지하기 위한 최소 소비전력을 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

• -10 ≤ temperature ≤ 40
• -10 ≤ t1 < t2 ≤ 40
  • temperature는 t1 ~ t2 범위 밖의 값입니다.
• 1 ≤ a, b ≤ 100
  • a는 에어컨의 희망온도와 실내온도가 다를 때의 1분당 소비전력을 나타냅니다.
  • b는 에어컨의 희망온도와 실내온도가 같을 때의 1분당 소비전력을 나타냅니다.
• 2 ≤ onboard의 길이 ≤ 1,000
  • onboard[i]는 0 혹은 1이며, onboard[i]가 1이라면 i분에 승객이 탑승 중이라는 것을 의미합니다.
  • onboard[0] = 0
  • onboard에 1이 최소 한 번 이상 등장합니다.
• 승객이 탑승 중인 시간에 쾌적한 실내온도를 유지하는 것이 불가능한 경우는 주어지지 않습니다.

 

 

풀이

이 문제는 바텀 업 방식의 다이나믹 프로그래밍으로 풀어야 합니다.

 

dp[시간][온도] = 이 시간 이 온도에 필요한 최소 소비전력 형태로 저장시킵니다.

저는 최초의 온도를 0일때로 해서, 0시 가동 이후의 온도를 1로 하여, dp[i+1][온도]가 i분 때의 에어컨 가동 후의 온도를 맟추는 최소전력입니다.

단, 온도의 범위가 영하부터이기 때문에, 최소 온도의 범위인 10을 모든 온도에 더해줍니다.

temperature, t1, t2에 각각 10씩 더해주면 됩니다.

온도의 유효한 범위는 min(temperature, t1) ~ max(temperature, t2)임을 알수있습니다.

 

그리고, 손님이 온 경우에는 온도 업데이트를 t1 ~ t2인 경우에만 해야합니다.

그게 아니라면, 유효한 범위 내에서 합니다.

온도 업데이트는 설정온도와 같은 말장난이 숨어있지만, 사실은 다음의 경우만 있습니다:

1. 온도를 1조정하는 경우(-1 또는 +1) : a만큼 소모

2. 온도를 유지하는 경우(+0) : b만큼 소모

3. 전원을 끔으로 (-1, +1, 0)온도 변경: 0만큼 소모

 

온도를 유지하지 않고, 조정하는 경우에는 이전의 온도가 유효한지 체크해야 합니다.

1도는 올리는 방법은 에어컨을 켜거나, 실외온도보다 낮은 경우인데, 이 때 t-1이 최소범위보다 큰거나 같은지 확인해야 합니다. (t-1이 유효하지 않다면, 업데이트할 수 없는 수치입니다.)

1도를 내리는 방법은 에어컨을 켜거나, 실외온도보다 높은 경우인데, 이 때 t+1(이전온도)이 최대범위보다 작거나 같은지 확인해야 합니다.

 

dp[time]은 time이 지나고 나서, 각 온도별로 가지고 있는 최소의 소비전력이 담겨 있습니다.

여기서 가장 작은 값을 반환해주면 됩니다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int solution(int temperature, int t1, int t2, int a, int b, vector<int> onboard) {
    temperature += 10;
    t1 += 10;
    t2 += 10;

    const int time = onboard.size();
    const int lowest = min(temperature, t1);
    const int highest = max(temperature, t2);

    vector<vector<int>> dp(time + 1, vector<int>(highest + 1, 1e6));
    dp[0][temperature] = 0;
    for (int i = 0; i < time; i++) {
        int from;
        int to;
        if (onboard[i]) {
            from = t1;
            to = t2;
        } else {
            from = lowest;
            to = highest;
        }

        for (int j = from; j <= to; j++) {
            // 온도 낮추기
            if (j + 1 <= highest) {
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j + 1] + a);
            }

            // 온두 높이기
            if (j - 1 >= lowest) {
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - 1] + a);
            }

            // 그냥 유지
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + b);

            // off
            //  껐을때 온도가 내려감.
            if (j+1 > temperature && j + 1 <= highest) {
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j + 1]);
            }

            // 껐을 때 온도가 올라감.
            if (j-1 < temperature && j - 1 >= lowest) {
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - 1]);
            }
            // 아니면 온도가 같다?
            if (j == temperature && j <= highest && j >= lowest){
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
            }
        }
    }

    // for (int i = 0; i <= time; i++){
    //     for (int j = lowest; j <= highest; j++)
    //     {
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << "onboard: " << onboard[i];
    //     cout << endl;
    // }

    return *min_element(dp[time].begin(), dp[time].end());
}