[프로그래머스] 에어컨

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/214289

---

풀이

어쩌다보니 또! DP 문제를 잡았다. DP 좀 그만 잡고 싶은데 고르는 문제마다 DP...🥹

dp[i][j] = i분일 때 j도를 유지하기 위한 최소 소비전력으로 두고 풀어나가면 된다.
현재 시간이 i, 현재 온도가 j일 때 고를 수 있는 선택지는 다음 4가지가 있다.

 

1. 에어컨 끄기
2. 온도 1도 올리기
3. 온도 1도 내리기
4. 온도 유지하기

문제를 잘 읽어보면 알겠지만 희망온도는 의미가 없다. 현재 온도가 26도라면, 희망온도를 40도로 설정하든 30도로 설정하든 똑같기 때문이다. 중요한 건 온도를 올릴지 내릴지이다.

온도 범위 보정

문제에서 주어지는 온도 범위는 -10도 이상, 40도 이하이다.
그런데 우리는 온도를 dp배열의 인덱스로 쓰고있다. 따라서 주어지는 온도(temperature, t1, t2)에 10을 더해주어야 한다.

 

int MAX_TEMP = 40, MIN_TEMP = -10, RANGE = MAX_TEMP-MIN_TEMP;

temperature-=MIN_TEMP;
t1-=MIN_TEMP;
t2-=MIN_TEMP;

 

점화식 세우기

문제에서 초기 온도==실외 온도라고 했으므로, dp[0][temperature]=0으로 두고 시작한다.
현재 시간이 i, 현재 온도가 j라고 가정하고 dp[i][j]를 이용해 시간이 i+1일 때의 값을 구해보자.

 

(1) 에어컨을 끄는 경우: 0원 소모

1. 현재 온도 < 실외 온도: 1도 증가
dp[i+1][j+1] = Math.min( dp[i][j], dp[i+1][j+1] )

2. 현재 온도 > 실외 온도: 1도 감소
dp[i+1][j-1] = Math.min( dp[i][j], dp[i+1][j-1] )

3. 현재 온도 == 실외 온도: 온도 변화 X
dp[i+1][j] = Math.min( dp[i][j], dp[i+1][j] )

 

(2) 온도를 1도 높이거나 낮추는 경우: a원 소모

온도를 1도 높이는 경우: dp[i+1][j+1] = Math.min( dp[i][j]+a, dp[i+1][j+1] )
온도를 1도 낮추는 경우: dp[i+1][j-1] = Math.min( dp[i][j]+a, dp[i+1][j-1] )

 

(3) 온도를 유지하는 경우: b원 소모 

dp[i+1][j] = Math.min( dp[i][j]+b, dp[i+1][j] )

 

최소 비용 구하기

onboard배열의 마지막 인덱스가 N이라고 하면, 최소 비용은 onboard[N]배열의 최솟값이다.
하지만 마지막 순간에 승객이 탑승하고 있었다면, 현재 온도가 온도 범위를 초과하는 경우는 제외하고 최소값을 구해야 한다.

 

int answer = MAX;
for (int j=0; j<=RANGE; j++) {
    if(onboard[onboard.length-1]==1 && (j<t1 || j>t2)) continue;
    answer = Math.min(dp[onboard.length-1][j], answer);
}

 

---

전체 코드

분당 최대 소비전력은 100, 최대 1000분이 주어지므로 MAX를 1,000,001로 설정했다.

 

import java.util.*;

class Solution {
    int[][] dp;
    int MAX = 1_000_001;
    int MAX_TEMP = 40, MIN_TEMP = -10, RANGE = MAX_TEMP-MIN_TEMP;
    public int solution(int temperature, int t1, int t2, int a, int b, int[] onboard) {
        if(t1<=temperature && temperature<=t2) return 0;

        temperature-=MIN_TEMP;
        t1-=MIN_TEMP;
        t2-=MIN_TEMP;

        dp = new int[onboard.length][RANGE+1];
        for (int i=0; i<dp.length; i++) {
            Arrays.fill(dp[i], MAX);
        }

        dp[0][temperature] = 0;

        for (int i=0; i<onboard.length-1; i++) {
            for (int j=0; j<=RANGE; j++) {
            	
                // 승객이 탑승했는데 온도 범위 밖인 경우 SKIP
                if(onboard[i]==1 && (j<t1 || j>t2)) continue;
                
                // 1. 에어컨을 끄는 경우
                int nextTemp = j;
                if(j<temperature && j<RANGE) nextTemp = j+1;
                else if(j>temperature && j>0) nextTemp = j-1;
                dp[i+1][nextTemp] = Math.min(dp[i][j], dp[i+1][nextTemp]);

                // 2. 희망온도!=현재온도
                if(j>0) dp[i+1][j-1] = Math.min(dp[i][j]+a, dp[i+1][j-1]);
                if(j<RANGE) dp[i+1][j+1] = Math.min(dp[i][j]+a, dp[i+1][j+1]);

                // 3. 희망온도==현재온도
                dp[i+1][j] = Math.min(dp[i][j]+b, dp[i+1][j]);
            }
        }

        int answer = MAX;
        for (int j=0; j<=RANGE; j++) {
            if(onboard[onboard.length-1]==1 && (j<t1 || j>t2)) continue;
            answer = Math.min(dp[onboard.length-1][j], answer);
        }

        return answer;
    }
}