[Algorithm] 프로그래머스 - 에어컨

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

접근

처음엔 그리디 알고리즘인가 했는데 처리해야 하는 케이스가 너무 많았다.

그렇다고 백트래킹으로 하기에도 문제 제한사항을 만족하기 어렵다.

다음으로 생각해본 게 DP인데 각 분마다 모든 온도에 대해 최소 비용을 저장하면 문제 해결이 가능하다고 생각했다.

단, 제한사항에 temperature의 범위가 $-10\leq{...}\leq{40}$ 이기 때문에 memoization하기 위해서는 온도에 관련된 입력 변수들에 10씩 더해 양의 정수로 만들어줘야 한다.

memoization을 위한 dp[i][j] 의 정의는 i 분에서 j 온도가 되기 위한 최소 비용이다.

최소 비용을 저장할 때 총 네 가지의 케이스를 고려해야 한다.

1. 에어컨을 꺼서 온도가 올라가는/내려가는 경우 → 비용 X
2. 현재 온도가 실외 온도와 같아 에어컨을 켤 필요가 없는 경우 → 비용 X
3. 현재 온도를 유지하기 위해 에어컨을 가동하는 경우 → 비용 b
4. 냉/난방을 위해 에어컨을 가동하는 경우 → 비용 a

이 네 가지 경우를 고려해 j 온도에서의 최소 비용을 저장하면 된다.

소스코드(Java)

class Solution {
    public int solution(int temperature, int t1, int t2, int a, int b, int[] onboard) {

        int[][] dp = new int[onboard.length][41+10];
        final int MAX_VALUE = 100 * 1000;

        t1 += 10;
        t2 += 10;
        temperature += 10;

        int delta = 1;
        if(t2 < temperature) {
            delta = -1;
        }

        for(int i = 0; i < onboard.length; i++) {
            for(int j = 0; j < 51; j++) {
                dp[i][j] = MAX_VALUE;
            }
        }

        dp[0][temperature] = 0;

        for(int i = 1; i < onboard.length; i++) {
            for(int j = 0; j < 51; j++) {
                int min = MAX_VALUE;
                if(onboard[i] == 0 || (onboard[i] == 1 && j >= t1 && j <= t2)) {
                    if(j+delta >= 0 && j+delta <= 50) {
                        min = Math.min(min, dp[i-1][j+delta]);
                    }
                    if(j == temperature) {
                        min = Math.min(min, dp[i-1][j]);
                    }
                    if(j >= t1 && j <= t2) {
                        min = Math.min(min, dp[i-1][j]+b);
                    }
                    if(j-delta >= 0 && j-delta <= 50) {
                        min = Math.min(min, dp[i-1][j-delta]+a);
                    }
                    dp[i][j] = min;
                }
            }
        }

        int result = dp[onboard.length-1][0];

        for(int i = 1; i < 51; i++) {
            result = Math.min(result, dp[onboard.length-1][i]);
        }

        return result;
    }
}