에어컨
문제 링크 : 에어컨
문제 설명
현대모비스에서 개발한 실내공조 제어 시스템은 차내에 승객이 탑승 중일 때 항상 쾌적한 실내온도(t1 ~ t21)를 유지할 수 있도록 합니다. 현재(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이 최소 한 번 이상 등장합니다.
- 승객이 탑승 중인 시간에 쾌적한 실내온도를 유지하는 것이 불가능한 경우는 주어지지 않습니다.
입출력 예
| temperature | t1 | t2 | a | b | onboard | result |
|---|---|---|---|---|---|---|
| 28 | 18 | 26 | 10 | 8 | [0, 0, 1, 1, 1, 1, 1] | 40 |
| -10 | -5 | 5 | 5 | 1 | [0, 0, 0, 0, 0, 1, 0] | 25 |
| 11 | 8 | 10 | 10 | 1 | [0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1] | 20 |
| 11 | 8 | 10 | 10 | 100 | [0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1] | 60 |
풀이 방법
- 최소 소비전력을 구하는 문제인데, 예시를 보았을 때 직관적으로 그리디하게 풀기에는 어려운 문제로 보였다. 따라서 dp를 통해 문제를 해결하고자 했다.
- 먼저 temperature와 t1, t2의 최소 값은 -10인데, dp를 정의하는 배열에서 인덱스를 음수로 할 수 없기 때문에, 각각의 변수에 10을 더해서 사용했다. dp 배열은 onboard의 최대값이 1000이고, t1 ~ t2의 범위 값의 최대값이 50이기 때문에 시간에 따른 온도를 저장하기 위해
int dp[1001][51];로 정의했다. 또한 소비전력의 최대값을 (onboard의 길이) * (a,b의 크기)로 정의할 수 있는데, 100,000을 초기값으로 지정했다. - onboard가 1인 경우에, 온도가 t1, t2 사이에 없을 경우에는 제외를 했다. 해당 경우를 제외하고는 3가지의 경우를 구분할 수가 있다.
- 에어컨을 끈 경우 : 현재 온도에 따라 실외온도에 맞춰서 이동
- 에어컨을 켜고, 온도를 수정하는 경우
- 에어컨을 켜고, 온도를 유지하는 경우
- 3가지의 경우를 통해 바텀업 방식을 통해서 문제를 해결했다.
-> 해당 문제풀이는 최악의 경우 (onboard의 길이) * (t1 ~ t2의 범위 길이)의 시간복잡도가 걸릴 것이고,O(1,000*50)만큼 걸릴 것으로 보인다.
구현
#include <string>
#include <vector>
using namespace std;
int solution(int temperature, int t1, int t2, int a, int b, vector<int> onboard) {
temperature += 10; t1 += 10; t2 += 10;
int dp[1001][51];
int n = onboard.size();
for(int i = 0; i < 1001; i++){
for(int j = 0; j < 51; j++){
dp[i][j] = 100000;
}
}
// 나올 수 있는 온도의 범위 : min(temperature, t1) ~ max(temperature, t2)
int min_temp = min(temperature, t1);
int max_temp = max(temperature, t2);
dp[0][temperature] = 0;
for(int i = 0; i < n - 1; i++){
for(int temp = min_temp; temp <= max_temp; temp++){
if((onboard[i] == 1) && (temp < t1 || temp > t2)){
continue;
}
// 1. 에어컨을 끈 경우
int next = temp;
if(temp < temperature && temp < max_temp) next = temp + 1;
else if(temp > temperature && temp > 0) next = temp - 1;
dp[i+1][next] = min(dp[i+1][next], dp[i][temp]);
// 2. 에어컨을 켜고, 온도를 다르게 수정하는 경우
if (temp > 0){
dp[i+1][temp-1] = min(dp[i+1][temp-1], dp[i][temp] + a);
}
if (temp < max_temp){
dp[i+1][temp+1] = min(dp[i+1][temp+1], dp[i][temp] + a);
}
// 3. 에어컨을 켜고, 온도를 같게 하는 경우
dp[i+1][temp] = min(dp[i+1][temp], dp[i][temp] + b);
}
}
int answer = 100000;
for(int temp = min_temp; temp <= max_temp; temp++){
if((onboard[n - 1] == 1) && (temp < t1 || temp > t2)) continue;
answer = min(answer, dp[n - 1][temp]);
}
return answer;
}