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

출처

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

프로그래머스

 

문제

 

이 문제는 에어컨을 적절하게 끄고 키며, 켜져있을때는 희망온도를 유지하거나 조절할 수 있는데 이때 전력 소비가 최소가 되도록 하는 문제이다. 다만 손님이 타있을 경우엔 적정온도를 항상 유지해야 한다.

풀이

이 문제는 DP를 활용해서 상태를 지속적으로 기록해주며 풀어야 하는 문제이다. 이 문제에서 우리는 경우를 아래와 같이 나눌 수 있다.

 

• 손님이 타고있는 경우, 적정온도를 유지할 수 없는 경우는 살펴보지 않는다
• 에어컨을 튼 경우
  • 지금 온도를 유지하는 경우
  • 지금 온도보다 희망온도가 낮아 내리는 경우
  • 지금 온도보다 희망 온도가 높아 올리는 경우
• 에어컨을 끄는 경우
  • 지금 온도가 실외와 같다면 유지
  • 실외 온도가 더 높다면 온도가 올라감
  • 실외 온도가 더 낮으면 온도가 내려감

이렇게 경우를 나누어 DP를 구성할 수 있다. 점화식은 아래와 같이 구성한다

DP[i][j] - i시간에 j 온도일 때 최소 전력

DP[i + 1][다음 온도] = Min(DP[i+1][다음 온도], DP[i][j] + 소비된 전력의 양)

 

또한, 마지막 정답을 구할때는 마지막 시간에 손님이 타있다면 적정온도 범위 내에서 최소값을 찾고 아니라면 전체 범위에서 최소값을 찾는다.

 

코드

import java.util.*;

class pgs214289 {
    private static final int MAX = 100 * 1000 + 1;

    public int solution(int temperature, int t1, int t2, int a, int b, int[] onboard) {
        // 실외 온도
        // -10의 인덱스는 접근할 수 없기 때문에, 전체적으로 10을 더해 인덱스 접근이 가능하도록 함.
        int temp = temperature + 10;
        t1 += 10;
        t2 += 10;
        int[][] dp = new int[onboard.length][51];
        for (int[] x : dp) {
            Arrays.fill(x, MAX);
        }
        dp[0][temp] = 0;
        for (int i = 0; i < onboard.length - 1; i++) {
            for (int j = 0; j < 51; j++) {
                // 승객 탑승시, 적정온도가 아니면
                if (onboard[i] == 1 && !(j >= t1 && j <= t2)) {
                    continue;
                }
                // 에어컨 On
                // 온도 유지
                dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j] + b);
                // 온도 내림
                if (j > 0) dp[i+1][j-1] = Math.min(dp[i+1][j-1], dp[i][j] + a);
                // 온도 올림
                if (j < 50) dp[i+1][j+1] = Math.min(dp[i+1][j+1], dp[i][j] + a);

                // 에어컨 Off
                if (temp == j) { // 온도 유지
                    dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j]);
                } else if (temp < j && j > 0) { // 온도 하강
                    dp[i+1][j-1] = Math.min(dp[i+1][j-1], dp[i][j]);
                } else if (temp > j && j < 50) { // 온도 상승
                    dp[i+1][j+1] = Math.min(dp[i+1][j+1], dp[i][j]);
                }
            }
        }
        int answer = MAX;
        for (int i = 0; i < 51; i++) {
            // 마지막에 승객 탑승시 적정온도가 아니라면
            if (onboard[onboard.length-1] == 1 && !(i >= t1 && i <= t2)) {
                continue;
            }
            answer = Math.min(answer, dp[onboard.length-1][i]);
        }

        return answer;
    }
}