프로그래머스 [Lv. 3] 에어컨 {언어 : JavaScript} [다시 풀어 보기]

문제 링크

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

프로그래머스

정답 코드

function solution(temperature, t1, t2, a, b, onboard) {
    // 계산을 편리하게 하기 위해서 -10 <= t <= 40인 범위를 0 <= t <= 50으로 바꾼다.
    const t = temperature + 10;
    t1 += 10;
    t2 += 10;
    const n = onboard.length;
    const dp = Array.from({length: n}, () => Array(51).fill(Infinity));
    dp[0][t] = 0;
    
    const isValid = (i, temp) => !onboard[i] || (t1 <= temp && temp <= t2);
    
    // ht 는 hope temperature
    for (let i = 0; i < n-1; i++) {
        for (let ht = 0; ht < 51; ht++) {
            if (dp[i][ht] === Infinity) {
                continue;
            }
            
            // 에어컨 끄는 경우
            const temp = ht < t ? ht+1 : ht > t ? ht-1 : ht;
            
            if (isValid(i+1, temp)) {
                dp[i+1][temp] = Math.min(dp[i+1][temp], dp[i][ht]);
            }
            
            // 에어컨을 작동시키는 경우
            for (const [newHt, cost] of [[ht+1, a], [ht-1, a], [ht, b]]) {
                if (!isValid(i+1, newHt) || -1 >= newHt || newHt >= 51) {
                    continue;
                }
                dp[i+1][newHt] = Math.min(dp[i+1][newHt], dp[i][ht] + cost);
            }
            
        }
    }
    
    const answer = Math.min(...(dp.at(-1)));
    return answer;
}

풀이 방법

 

1. 주어진 온도 범위를 0부터 50까지로 변환하여 계산의 편리성을 높인다.
2. dp 배열을 사용해 시간별 가능한 온도 상태를 추적하며 최소 비용을 저장한다.
3. 초기 상태로 현재 온도에서 비용 0을 설정하고, 나머지 온도는 무한대로 초기화한다.
4. 각 시간대에서 현재 온도 ht에 대해 온도를 변경하지 않고 유지하거나, 증가 또는 감소시켜 에어컨을 작동하지 않는 경우를 처리한다.
5. 에어컨을 작동하는 경우 온도를 1도 올리거나 내리거나 유지할 수 있으며, 이때 각각의 비용을 고려하여 dp 배열을 업데이트한다.
6. 각 경우의 온도 변화를 검토할 때, 설정된 온도 범위를 벗어나지 않는지 검증한다.
7. 마지막 시간대에서 최소 비용을 찾기 위해 dp 배열의 마지막 행에서 가장 작은 값을 구한다.
8. 최종 최소 비용을 반환하여, 주어진 조건을 만족하면서 온도 조절에 드는 최소 비용을 계산한다.

 

 

느낀점

• dp일거라고 생각은 했으나 이렇게도 풀 수 있다는 것을 알았다.
• 파이썬이나 Java로 다시 풀어보자.