프로그래머스 에어컨 (JAVA)

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

프로그래머스

 

저는 dfs를 통해 문제를 해결하였습니다.

현재 온도와 실내 온도를 비교하여 다음 온도를 정하고, 현재 만약에 사람이 존재한다면 , t1 t2 사이에 온도가 있는지를 확인하고 사이값이라면 계속 진행합니다. 그 중 가장 낮은 값을 찾아 결과값으로 도출하였습니다.

 

import java.util.*;

class Solution {
    private static final int ON = 1;
    private static final int OFF = 0;
    private static final int STANDARD = 10;
    private static final int MAX_VALID = 100;
    public int solution(int temperature, int t1, int t2, int a, int b, int[] onboard) {
        int[][] dp = new int[onboard.length][MAX_VALID+STANDARD];
        for(int i = 0 ; i < onboard.length ; i++){
            Arrays.fill(dp[i], NOT_VALID);
        }
        int answer = cal(0,temperature,temperature,t1,t2,a,b,onboard,dp);
        return answer;
    }
    private static final int INF = 987654321;
    private static final int NOT_VALID = -1;
    private static int cal(int depth,int outTemp,int inTemp, int t1, int t2, int a, int b,int[] onboard,
                          int[][] dp){
        if(depth == onboard.length){
            return 0;
        }
        if(inTemp + STANDARD < 0 || inTemp + STANDARD >= MAX_VALID){
            return INF;
        }
        if(onboard[depth] == ON && (inTemp < t1 || inTemp > t2) ){
            return INF;
        }
        if(dp[depth][inTemp + STANDARD] != NOT_VALID){
            return dp[depth][inTemp + STANDARD];
        }
        int result = INF;
        if(outTemp < inTemp){
            result = Math.min(result, cal(depth+1,outTemp,inTemp+1,t1,t2,a,b,onboard,dp) + a); 
            result = Math.min(result, cal(depth+1,outTemp,inTemp-1,t1,t2,a,b,onboard,dp));
        }
        if(outTemp > inTemp){
            result = Math.min(result, cal(depth+1,outTemp,inTemp-1,t1,t2,a,b,onboard,dp) + a);
            result = Math.min(result, cal(depth+1,outTemp,inTemp+1,t1,t2,a,b,onboard,dp));
        }
        if(outTemp == inTemp){
            result = Math.min(result, cal(depth+1,outTemp,inTemp+1,t1,t2,a,b,onboard,dp) + a);
            result = Math.min(result, cal(depth+1,outTemp,inTemp-1,t1,t2,a,b,onboard,dp) + a);
            result = Math.min(result, cal(depth+1,outTemp,inTemp,t1,t2,a,b,onboard,dp));
        }else{
            result = Math.min(result, cal(depth+1,outTemp,inTemp,t1,t2,a,b,onboard,dp) + b);
        }
        dp[depth][inTemp + STANDARD] = result;
        return result;
    }
}