이번 문제는 프로그래머스의 레벨 3 에어컨 문제이다.
레벨 3부터는 참 풀이를 생각해내기가 어려운 것 같다.
문제를 차근차근 읽어보자.

자동차에 실내 공조 제어시스템이 부착되어있다.
승객이 탑승했을 때, 실내 온도를 쾌적하게 유지하는 장치이다.
최소한의 전력으로 승객에게 쾌적한 실내 온도를 제공해주도록 하자.

희망온도까지 실내 온도를 조정하기 위한 소비 전력과,
희망온도와 실내 온도가 같을 때의 유지 전력이 주어진다.
에어컨을 껐을 때는 실내 온도가 자동으로 실외 온도에 맞추어 진다.
시작 온도는 실외 온도와 동일하다.

상당히 복잡한 조건이다, 우선 알고리즘을 분류해보자.

알고리즘 파악

먼저 이 문제는 미래를 내다 보아야 하는 것처럼 보인다.
알맞는 희망온도를 매 순간 정하여, 최소 전력만을 사용해야 하기 때문이다.
그럼 Greedy하게 풀 수 있는 문제인걸까?

에어컨을 끌 지, 켤 지 또는 희망온도가 어떻게 될 지 모두 선택해야 한다.
즉, Greedy 하게 단순화해서 풀 수는 없는 문제인 것 같다.

사실 가장 유력해보이는 풀이는 동적 계획법이라고 생각한다.
어떤 시점에서 온도의 방향을 정하여 다음 시점의 소비전력이 결정된다.
즉, 어떤 시점의 선택에 따라 그 시점까지의 소비전력이 정해진다.
해당 시점까지 항상 최소 전력을 고집하며 끝까지 진행한다면,
마지막엔 결국 목표한 최소 전력을 구하는 방식이 될 것이다.

DP

이제 동적 계획법으로 문제를 어떻게 풀 것인지 생각해보자.
우리가 선택할 수 있는 선택지들을 생각해보자.

  1. 에어컨을 켜 희망온도 내려 범위내로 온도를 내린다.
  2. 에어컨을 켜 희망온도를 올려 범위내로 온도를 올린다.
  3. 에어컨을 켜 희망온도를 실내온도와 맞춰 쾌적하게 유지시킨다.
  4. 에어컨을 꺼 실내온도를 실외온도에 맞춘다.

내 생각에는 최소한 2차원의 memoization용 배열이 필요할 것 같다.
이제 각 행렬이 어떤 변인을 의미하는 지 정해야 한다.

먼저 가장 중요한 변인은 시간이다.
그래서 나는 시간을 행으로 지정하도록 하겠다.
그 다음으로 중요한 변인은 온도라고 생각한다.
온도는 에어컨을 통해 우리가 조종할 수 있는 유일한 항목이다.
따라서 열을 온도를 의미하도록 지정한다.

다시 말해, dp[i][j]는 j분에 i도까지 맞추는데에 드는 비용이 된다.
이제 우리는 이 dp 배열을 어떻게 채워나갈지 고민해야 한다.
우리는 아래의 경우와 같이 나누어 dp 배열을 채울 수 있다.

  1. 에어컨을 트는 경우
    • 현재 온도가 최대 온도보다 낮으면 주어진 a 전력을 들여 온도를 내릴 수 있다.
    • 현재 온도가 최저 온도보다 높으면 주어진 a 전력을 들여 온도를 내릴 수 있다.
    • 현재 온도와 상관없이, 주어진 b 전력을 들여 온도를 유지할 수 있다.
  2. 에어컨을 끄는 경우
    • 전력을 들이지 않고, 실외 온도에 따라 온도가 내려간다.
      • 실외 온도에 따라 온도가 내리려면, 현재 온도는 실외 온도보다 높아야 한다.
    • 전력을 들이지 않고, 실외 온도에 따라 온도가 올라간다.
      • 실외 온도에 따라 온도가 내리려면, 현재 온도는 실외 온도보다 낮아야 한다.
    • 전력을 들이지 않고, 실외 온도가 유지된다.
      • 이는 실내 온도와 실외 온도가 같아야 한다.

또한 추가적으로 효율적인 계산을 위해 최대 온도와 최소 온도에 대해 생각해보자.
온도를 조절을 할 때, 굳이 t1과 t2를 벗어날 필요가 있을까?
중간에 굳이 벗어나면 에어컨을 켜야하므로, 전력에 낭비가 생긴다.
따라서 t1, t2를 벗어나는 경우는 고려할 필요가 없다!

또, 에어컨을 계속 끄고 있으면 실외 온도와 같은 온도까지 변할 수 있다.
즉 min(t1, 실외 온도) ~ max(t2, 실외 온도)까지 움직일 수 있다.

위의 모든 경우 중 최소를 계산하며 점점 마지막 시간까지 쌓아나간다.
그럼 분명 마지막 시간 축의 최소 값은 결과적으로 최소 비용이 될 것이다.
최종적으로 아래와 같이 구현된다.

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

	temperature += 10; t1 += 10; t2 += 10;
	init_dp(temperature, onboard);

	int min_temp = min(t1, temperature);
	int max_temp = max(t2, temperature);
	for (int i = 1; i <= onboard.size(); i++) {
		int lower_temp_bound = min_time;
		int upper_temp_bound = max_time;
		// 어차피 t1, t2 혹은 실외온도를 벗어나는 것은 비효율적이다.
		if (onboard[i]) {
			lower_temp_bound = t1;
			upper_temp_bound = t2;
		}

		for (int j = lower_temp_bound; j <= upper_temp_bound; j++) {
			// 에어컨이 켜지는 경우들
			if (j + 1 <= max_temp)
				dp[j][i] = min(dp[j][i], dp[j + 1][i - 1] + a);
			if (j - 1 >= min_temp)
				dp[j][i] = min(dp[j][i], dp[j - 1][i - 1] + a);
			dp[j][i] = min(dp[j][i], dp[j][i - 1] + b);

			// 에어컨이 꺼지는 경우들
			if ((j + 1 > temperature) && (j + 1 <= max_temp))
				dp[j][i] = min(dp[j][i], dp[j + 1][i - 1]);
			if ((j - 1 < temperature) && (j - 1 >= min_temp))
				dp[j][i] = min(dp[j][i], dp[j - 1][i - 1]);
			if ((j == temperature) && (j <= max_temp) && (j >= min_temp))
				dp[j][i] = min(dp[j][i], dp[j][i - 1]);
		}
	}

	for (int i = 0; i <= 50; i++)
		answer = min(dp[i][onboard.size() - 1], answer);
	return answer;
}

배열을 채우는 조건을 혼자서 생각해 내기에는 어려운 문제였다.
이런 문제를 풀며 익숙해지고 잘 풀게 되어야 할 것이다.