프로그래머스 에어컨 - C++ 풀이

---

 

1. dp(currTemp, t): 현재 시각이 t초이고, 현재 온도가 currTemp일 때 남은 시간동안 쾌적함을 유지하기 위한 최소비용
2. 1도 올리는 경우, 1도 내리는 경우, 희망온도를 현재온도로 유지하는 경우, 아예 끄는 경우 중 비용이 최소인 경우를 선택한다.

 

1. dp(currTemp, t): 현재 시각이 t초이고, 현재 온도가 currTemp일 때 남은 시간동안 쾌적함을 유지하기 위한 최소비용

dp(currTemp, t)를 위와 같이 정의하자.

 

2. 1도 올리는 경우, 1도 내리는 경우, 희망온도를 현재온도로 유지하는 경우, 아예 끄는 경우 중 비용이 최소인 경우를 선택한다.

 어차피 온도는 1초마다 1씩만 내려가거나 올라갈 수 있다. 따라서 희망온도는 신경쓰지 않아도 된다. 현재 온도가 7도라고 하자. 만약 1초 뒤에 온도가 올라서 8도가 되는 경우는 희망온도를 8도로 맞췄다 치면 되고, 1초 뒤에 온도가 떨어져 6도가 되는 경우는 희망온도를 6도로 맞췄다고 치면 되기 때문이다. 따라서 현재 시각에서 할 수 있는 행동의 종류는 총 4가지이다. 이 중 최소 비용인 경우를 선택하면 된다.

1. 1도 올리기
     : 현재온도와 희망온도가 다르므로 에어컨 가동 비용이 A만큼 발생한다.
     : A + dp(currTemp + 1, t + 1)
2. 1도 내리기 = A + dp(currTemp + 1, t + 1)
     : 현재온도와 희망온도가 다르므로 에어컨 가동 비용이 A만큼 발생한다.
     : A + dp(currTemp - 1, t + 1)
3. 희망온도 유지하기
     : 희망온도를 현재 온도로 유지하는 비용은 B이다.
     : B + dp(currTemp, t + 1)
4. 끄기
     : 에어컨을 끄는 경우 실외온도 쪽으로 1도 이동한다. 이 온도를 nextTemp라하면
     : dp(nextTemp, t + 1)

 

---

#include <string>
#include <vector>
#include <string.h>
#include <iostream>

using namespace std;

const int MAX_TEMP = 3050;
const int MAX_N = 1010;
const int INF = 987654321;

int N, outsideTemp;
int A, B, T1, T2;
int cache[MAX_TEMP][MAX_N];
vector<int> onBoard;

int nextTemp(int currTemp) {
    int gap = outsideTemp - currTemp;
    
    if (gap > 0) return currTemp + 1;
    else if (gap < 0) return currTemp - 1;
    else return currTemp;
}

int dp(int currTemp, int t) {
    if (t == N) return 0;
    if (onBoard[t] && (currTemp < T1 || currTemp > T2)) return INF;
    
    int& ret = cache[currTemp+1050][t];
    if (ret != -1) return ret;
    
    ret = INF;
    // 그냥 켜놓기
    ret = min(ret, B + dp(currTemp, t+1));
    // 온도 낮추기
    ret = min(ret, A + dp(currTemp-1, t+1));
    // 온도 높이기
    ret = min(ret, A + dp(currTemp+1, t+1));
    // 끄기
    ret = min(ret, dp(nextTemp(currTemp), t+1));
    
    return ret;
}

int solution(int temperature, int t1, int t2, int a, int b, vector<int> onboard) {
    int answer = INF;
    outsideTemp = temperature;
    T1 = t1;
    T2 = t2;
    A = a;
    B = b;
    N = onboard.size();
    onBoard = onboard;
    
    memset(cache, -1, sizeof(cache));
    answer = dp(temperature, 0);
    
    return answer;
}