문제

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

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

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

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

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

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

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

제한사항

• -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문제..지만 다른 방법으로 풀다가 많이 헤맸다..

1. 온도 기준 잡기

실내 온도를 내릴 때와 올릴 때의 비용이 모두 a로 같으므로 희망온도 구간과 temperature이 얼마나 차이 나는 지가 중요하다. 따라서 기온인 temperature이 희망온도 구간보다 높은 지나 낮은 지, 실제 온도가 몇인 지는 중요하지 않기 때문에 계산의 편리를 위해 temperature를 0으로 기준 삼고 희망온도 구간이 항상 더 높도록 설정했다.

		if(temperature > t2){
            temperature = t1 - (temperature - t2);
        }
        
        t1 = t1 - temperature;
        t2 = t2 - temperature;
        temperature = 0;

2. dp 범위 설정하기

설정 후 변수 상태는 temperature(0) < t1 < t2 이다. temperature 아래로는 일부러 온도를 내리지 않는 이상 내려가지 않고 내릴 필요도 없다. 또 온도를 t2 위로 올리는 것도 효율적이지 않기 때문에 실내온도 구간은 0 <= 실내온도 <= t2 이다. 풀땐 확신이 안 들어서 나올 수 있는 최대 범위인 0~50으로 풀었다 ㅎㅎ..

		//dp[시간][온도]
		int dp[][] = new int[onboard.length][t2+1];
        for(int i = 0; i < dp.length; i++){
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][temperature] = 0;

dp의 구간도 마찬가지이다. 처음 실내온도는 temperature이기 때문에 dp[0][temperature]는 0으로 초기화한다.

3.Bottom-up!

dp의 범위도 설정했으니 이제 쌓아 올려갈 일만 남았다. 시간(onboard의 길이)과 온도, 두 요소로 이중 for 문을 돌면서 dp[시간][온도]에 해당 시간에 해당 온도를 만들 수 있는 최소 비용을 저장한다.

	for(int i = 0; i< onboard.length-1; i++){
           //탐색 범위
           int low = 0, high = t2;
           if(onboard[i] == 1){
               low = t1;
           }
           for(int j = low; j <= high; j++){
               if(dp[i][j] == Integer.MAX_VALUE){
                   continue;
               }
               //```---------

onboard[시간]이 1일 경우 승객이 있다는 뜻이므로 탐색 범위를 희망온도인 t1~t2로 제한한다.

온도 조절을 위해 할 수 있는 행동은 온도 올리기, 온도 내리기, 온도 유지 - 3가지이다.

				if(j == temperature){
                   dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j]); 
                }
                else{
                   dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j] + b); 
                }
                
                if(j < t2 ){
                   dp[i+1][j+1] = Math.min(dp[i+1][j+1], dp[i][j] + a); 
                }
                
                if(j > temperature){
                   dp[i+1][j-1] = Math.min(dp[i+1][j-1], dp[i][j]); 
                }

온도를 유지할 땐 b의 비용이 필요하다. 다만 온도가 temperature(0)일 경우 필요 비용은 0이다.
온도를 올리고 내릴땐 a의 비용이 필요하다. 조절 후의 온도가 dp 범위 안에 있을 수 있게 제한한다.

		int answer = Integer.MAX_VALUE;
        
        int low = 0, high = t2;
        if(onboard[onboard.length-1] == 1){
            low = t1;
        }
        for(int j = low; j <= high; j++){
            answer = Math.min(answer, dp[dp.length - 1][j]);
        }

dp[마지막 시간]에서 탐색 범위에 있는 값 중 최소값이 정답이다.

코드

import java.util.*;

class Solution {
    
    public int solution(int temperature, int t1, int t2, int a, int b, int[] onboard) {
        if(temperature > t2){
            temperature = t1 - (temperature - t2);
        }
        
        t1 = t1 - temperature;
        t2 = t2 - temperature;
        temperature = 0;
        
        int dp[][] = new int[onboard.length][t2+1];
        for(int i = 0; i < dp.length; i++){
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][temperature] = 0;
        
        for(int i = 0; i< onboard.length-1; i++){
            
            int low = 0, high = t2;
            if(onboard[i] == 1){
                low = t1;
            }
            for(int j = low; j <= high; j++){
                if(dp[i][j] == Integer.MAX_VALUE){
                    continue;
                }
                
                if(j == temperature){
                   dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j]); 
                }
                else{
                   dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j] + b); 
                }
                
                if(j < t2 ){
                   dp[i+1][j+1] = Math.min(dp[i+1][j+1], dp[i][j] + a); 
                }
                
                if(j > temperature){
                   dp[i+1][j-1] = Math.min(dp[i+1][j-1], dp[i][j]); 
                }
                
            }
        }
        
        int answer = Integer.MAX_VALUE;
        
        int low = 0, high = t2;
        if(onboard[onboard.length-1] == 1){
            low = t1;
        }
        for(int j = low; j <= high; j++){
            answer = Math.min(answer, dp[dp.length - 1][j]);
        }
        

        return answer;
    }
}