[JAVA] 프로그래머스 LEVEL3 에어컨

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

프로그래머스

코딩테스트 연습 > 2023 현대모비스 알고리즘 경진대회 예선 > 에어컨

 

문제 분석

난이도: LEVEL3

문제 설명 

시작 온도 

실내공조 제어 시스템은 차내에 승객이 탑승 중일 때 항상 쾌적한 실내온도(t1 ~ t2)를 유지할 수 있도록 한다.

현재(0분) 실내온도는 실외온도와 같다.

 

에어컨 on

실내공조 제어 시스템은 실내온도를 조절하기 위해 에어컨의 전원을 켜 희망온도를 설정

희망온도는 에어컨의 전원이 켜져 있는 동안 원하는 값으로 변경할 수 있다.

실내온도와 희망온도가 다르다면 1분 뒤 실내온도가 희망온도와 같아지는 방향으로 1도 상승 또는 하강

실내온도가 희망온도와 같다면 에어컨이 켜져 있는 동안은 실내온도가 변하지 않는다.

 

에어컨 off

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

실내온도와 실외온도가 같다면 실내온도는 변하지 않는다.

 

에어컨의 소비전력 

에어컨의 소비전력은 현재 실내온도에 따라 달라집니다. 

에어컨의 희망온도와 실내온도가 다르다면 매 분 전력을 a만큼 소비하고, 희망온도와 실내온도가 같다면 매 분 전력을 b만큼 소비한다.

에어컨이 꺼져 있다면 전력을 소비하지 않으며, 에어컨을 켜고 끄는데 필요한 시간과 전력은 0이라고 가정

 

실내공조 제어 시스템

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

문제 예시

실외온도 28도/ t1 = 18 /  t2 = 26 / a = 10 / b = 8

승객이 탑승 중인 2 ~ 6분의 실내온도를 18(t1) ~ 26(t2)도 사이로 유지해야 한다.

 

방법1 ( 2 ~ 6분의 실내온도를 쾌적한 온도로 유지하는 방법1 )

0분은 실내온도가 실외온도와 동일하게 시작 

 

에어컨의 소비전력

0 ~ 1: 실내온도 != 희망온도 a * 2 = 20 

2 ~ 5: 실내온도 == 희망온도 b * 4 = 32 

 

소비전력: 32 + 20 = 52 

 

방법2 ( 2 ~ 6분의 실내온도를 쾌적한 온도로 유지하는 방법2 )

 

0 ~ 3: (4 * 10) = 40 

4 ~ 6: 소비 X

 

소비전력: 32 + 20 = 40 

이보다 소비전력이 적어지는 방법은 없다. 

 

틀린 코드1(28.0)

import java.util.*;
class Solution {
    static int min = 100 * 1000;
    static int T1, T2, A, B, Temperature, size;
    static int [] onBoard;
    public int solution(int temperature, int t1, int t2, int a, int b, int[] onboard) {
        T1 = t1;
        T2 = t2;
        A  = a;
        B  = b;
        Temperature = temperature;
        size = onboard.length; 
        onBoard = Arrays.copyOf(onboard, onboard.length);
        int cur = temperature;     // 0분에서 실내 온도 = 실외 온도
        calculate(0, cur, 0);
        
        return min;
    }
    public static void calculate(int depth, int cur, int sum){
        // 종료 
        if(depth == size){
            min = Math.min(min, sum);
            return;
        }
        // 승객이 탑승 중인 시간에 쾌적한 실내온도 X
        if(onBoard[depth] == 1 && (cur < T1 | T2 < cur)){
            return;
        }
        // 에어컨 ON
        
        // up = 희망온도와 다른 경우 
        calculate(depth + 1, cur + 1, sum + A);
        // down = 희망온도와 다른 경우 
        calculate(depth + 1, cur - 1, sum + A);
        // 희망온도와 같은 경우 
        calculate(depth + 1, cur, sum + B);
        
        // 에어컨 OFF
        if(Temperature > cur){
            calculate(depth + 1, cur + 1, sum);
        }
        else if(Temperature == cur){
            calculate(depth + 1, cur, sum);
        }
        else{
            calculate(depth + 1, cur - 1, sum);
        }
    }
}

18/25

18개 시간 초과 

onboard 크기를 이제 확인했다. onboard 크기는 1000이다. 

최악의 상황으로 계산하면 4^1000 이니까 말도 안 되는 시간 복잡도이다. 

DP로 풀어야 할듯하다.

 

정답 코드 (DP 활용) 

import java.util.*;
class Solution {
    static final int MAX = 100 * 1000 + 1;
    public int solution(int temperature, int t1, int t2, int a, int b, int[] onboard) {
        t1 += 10; t2 += 10; int temp = temperature + 10;
        
        int [][] DP = new int [onboard.length][51];
        for(int i = 0; i < onboard.length; i++){
            Arrays.fill(DP[i], MAX);
        }
        DP[0][temp] = 0; // 시작 온도 = 실외 온도
        for(int i = 0; i < onboard.length - 1; i++){
            for(int j = 0; j <= 50; j++){
                if(onboard[i] == 1 && (j < t1 || t2 < j)) continue; // 승객 탑승 시점에 적정 온도가 아니라면 
                // 에어컨 ON + 현재 온도 유지 - use b
                DP[i+1][j] = Math.min(DP[i+1][j], DP[i][j] + b);
                // 에어컨 ON + 현재 온도에서 down - use a
                if(j >= 1) DP[i+1][j-1] = Math.min(DP[i+1][j-1], DP[i][j] + a);
                // 에어컨 ON + 현재 온도에서 up - use 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 < 50){ // 온도 up
                    DP[i+1][j+1] = Math.min(DP[i+1][j+1], DP[i][j]);
                }
                else if(temp < j && j >= 1){ // 온도 down 
                    DP[i+1][j-1] = Math.min(DP[i+1][j-1], DP[i][j]);
                }
            }
        }
        int min = MAX;
        int last = onboard.length - 1;
        for(int i = 0; i <= 50; i++){
            if(onboard[last] == 1 && (i < t1 || t2 < i)) continue; // 마지막에 승객이 탑승했다면 적정 온도만 가능 
            min = Math.min(min, DP[last][i]);
        }
        return min;
    }
}

 

DP[i][j] 의미 

i 시간에 j 온도를 맞추는데 필요한 최소한의 에너지 

 

DP 범위 

온도의 범위는 -10 ~ 40 이다. 

배열에는 - 인덱스는 불가능하다. 

그래서 10씩 추가 

 t1 += 10; t2 += 10; int temp = temperature + 10;
 int [][] DP = new int [onboard.length][51];

 

가장 많은 에너지 소비 

onboard 최대 길이: 1000

a,b 최대 크기: 100 

1000 * 100 = 100000 

 static final int MAX = 100 * 1000 + 1;

 

DP 배열 초기화 

for(int i = 0; i < onboard.length; i++){
    Arrays.fill(DP[i], MAX);
}
DP[0][temp] = 0; // 시작 온도 = 실외 온도

시작 온도는 실외 온도와 동일하다.

 

핵심 로직 

for(int i = 0; i < onboard.length - 1; i++){
    for(int j = 0; j <= 50; j++){
        if(onboard[i] == 1 && (j < t1 || t2 < j)) continue; // 승객 탑승 시점에 적정 온도가 아니라면 
        // 에어컨 ON + 현재 온도 유지 - use b
        DP[i+1][j] = Math.min(DP[i+1][j], DP[i][j] + b);
        // 에어컨 ON + 현재 온도에서 down - use a
        if(j >= 1) DP[i+1][j-1] = Math.min(DP[i+1][j-1], DP[i][j] + a);
        // 에어컨 ON + 현재 온도에서 up - use 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 < 50){ // 온도 up
            DP[i+1][j+1] = Math.min(DP[i+1][j+1], DP[i][j]);
        }
        else if(temp < j && j >= 1){ // 온도 down 
            DP[i+1][j-1] = Math.min(DP[i+1][j-1], DP[i][j]);
        }
    }
}

 

1차 for문 onboard 길이만큼 

2차 for문 0 ~ 50 가능한 온도만큼 

 

필터링 조건 

if(onboard[i] == 1 && (j < t1 || t2 < j)) continue;

 

현재 시간이 승객 탑승 시점인데 적정 온도가 아니라면 해당 경우는 불가능한 경우다. 그래서 continue 

 

정리하면 총 6가지 케이스가 나온다.

1. 에어컨 사용 온도 유지 에너지 사용 b

2. 에어컨 사용 온도 up    에너지 사용 a

3. 에어컨 사용 온도 down 에너지 사용 a

4. 에어컨 사용 x 온도 유지 에너지 사용 0

5. 에어컨 사용 x 온도 up 에너지 사용 0

6. 에어컨 사용 x 온도 down 에너지 사용 0

 

에어컨 사용 x 케이스는 현재 온도에 맞추어서 자연스럽게 동작한다. 

실외 온도와 현재 온도가 같으면 유지 

실외 온도가 현재 온도와 다르면 += 1 

 

에어컨 사용 케이스 

// 에어컨 ON + 현재 온도 유지 - use b
DP[i+1][j] = Math.min(DP[i+1][j], DP[i][j] + b);
// 에어컨 ON + 현재 온도에서 down - use a
if(j >= 1) DP[i+1][j-1] = Math.min(DP[i+1][j-1], DP[i][j] + a);
// 에어컨 ON + 현재 온도에서 up - use a
if(j < 50) DP[i+1][j+1] = Math.min(DP[i+1][j+1], DP[i][j] + a);

 

에어컨 사용X 케이스 

// 에어컨 OFF
if(temp == j){     // 온도 유지 
    DP[i+1][j] = Math.min(DP[i+1][j], DP[i][j]);
}
else if(temp > j && j < 50){ // 온도 up
    DP[i+1][j+1] = Math.min(DP[i+1][j+1], DP[i][j]);
}
else if(temp < j && j >= 1){ // 온도 down 
    DP[i+1][j-1] = Math.min(DP[i+1][j-1], DP[i][j]);
}

 

가장 에너지 소비가 적은 케이스 고르기 

int min = MAX;
int last = onboard.length - 1;
for(int i = 0; i <= 50; i++){
    if(onboard[last] == 1 && (i < t1 || t2 < i)) continue; // 마지막에 승객이 탑승했다면 적정 온도만 가능 
    min = Math.min(min, DP[last][i]);
}
return min;