프로그래머스 에어컨 python, java

처음에는 백트래킹으로 접근해서 풀어볼려고 했는데 실패했다.
그후 DP로 해결할 수 있다는 힌트를 얻어 풀이했다.

📜 문제 바로 가기 : 에어컨

제출코드

파이썬

def solution(temperature, t1, t2, a, b, onboard):
    k = 1000 * 100
    t1 += 10
    t2 += 10
    temperature += 10
    
    # DP[i][j] : i분에 j 온도를 만들 수 있는 가장 적은 전력
    DP = [[k] * 51 for _ in range(len(onboard))] # j = 0 : -10 // = 50 : 40
    DP[0][temperature] = 0
    
    flag = 1 # 에어컨을 가동했을때 온도가 변하는 방향
    if temperature > t2 :
        flag = -1
 
    for i in range(1, len(onboard)):
        for j in range(51):
            arr = [k]
            if (onboard[i] == 1 and t1 <= j <= t2) or onboard[i] == 0:
                # 1. 에어컨을 키지 않고 실외온도와 달라서 실내온도가 -flag 되는 경우
                if 0 <= j+flag <= 50 :
                    arr.append(DP[i-1][j+flag])
                # 2. 에어컨을 키지 않고 현재온도 j 가 실외온도랑 같아서 변하지 않는 경우
                if j == temperature:
                    arr.append(DP[i-1][j])
                # 3. 에어컨을 키고 현재온도가 변하는 경우
                if 0 <= j-flag <= 50:
                    arr.append(DP[i-1][j-flag] + a)
                # 4. 에어컨을 키고 현재온도가 희망온도라서 온도가 변하지 않는경우
                if t1 <= j <= t2:
                    arr.append(DP[i-1][j] + b)

                DP[i][j] = min(arr)
            
    answer = min(DP[len(onboard)-1])
    return answer

자바

class Solution {
    final static Solution method = new Solution();
    
    public int solution(int temperature, int t1, int t2, int a, int b, int[] onboard) {
        int k = 1000 * 100;
        t1 += 10;
        t2 += 10;
        temperature += 10;
        
        int[][] DP = new int[onboard.length][51];
        for (int i = 0; i < onboard.length; i++) {
            for (int j = 0; j < 51; j++) {
                DP[i][j] = k;
            }
        }
        
        DP[0][temperature] = 0;
        
        int flag = 1;
        if (temperature > t2) {
            flag = -1;
        }
        
        for (int i = 1; i < onboard.length; i++) {
            for (int j = 0; j < 51; j++) {
                int minV = k;
                if (( onboard[i] == 1 && t1 <= j && j <= t2 ) || onboard[i] == 0) {
        
                    if (0 <= j+flag && j+flag <= 50) {
                        minV = method.min(minV, DP[i-1][j+flag]);
                    }
                    
                    if (j == temperature) {
                        minV = method.min(minV, DP[i-1][j]);
                    }

                    if (0 <= j-flag && j-flag <= 50) {
                        minV = method.min(minV, DP[i-1][j-flag] + a);
                    }
                    
                    if (t1 <= j && j <= t2) {
                        minV = method.min(minV, DP[i-1][j] + b);
                    }
                    
                    DP[i][j] = minV;
                    
                }
            }
        }
        
        int i = onboard.length-1;
        int answer = DP[i][0];
        for (int j = 1; j < 51; j++) {
            answer = method.min(answer, DP[i][j]);
        }
        return answer;
    }
    
    public int min(int a, int b) {
        if (a < b) {
            return a;
        } else {
            return b;
        }
    }
}

---

접근 방법

에어컨이 냉방으로 동작할 수도 있고 난방으로 동작할 수도 있다.
이를 판단하기 위해서 flag를 설정하였다.

DP 배열은 2차원 배열로 DP[i][j] 에는 i분에서 j온도를 달성하기 위한 최소 전력을 표시한다.
배열의 초기값 k는 문제 조건상 전력이 가장 크게 될 수 있는 1000*100 으로 설정했다.
또한 온도범위가 -10 ~ 40 이라서 인덱스를 맞춰주기 위해 필요한 부분에 10을 더해주었다.

DP 배열을 채우기 위한 조건 분기는 다음과 같다.

• i분 j온도에서 손님이 있을 경우 j가 쾌적온도(t1 ~ t2) 범위안에 있어야 한다. 손님이 없다면 상관없다.
• 에어컨을 키지 않는 경우
  - 실외온도가 실내온도와 차이가 나서 실내 온도가 -flag 방향으로 변하는 경우
  - 실외온도와 실내온도의 차이가 없어서 온도가 변하지 않는 경우
• 에어컨을 키는 경우
  - 실내온도가 희망온도와 달라서 온도가 +flag방향으로 변하는 경우
  - 실내온도가 희망온도와 같아서 온도가 유지되는 경우

맨 위 조건이 맞다면 4가지 경우에서 전력이 가장 적은 값을 DP[i][j]에 저장한다.