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

문제 설명

실내공조 제어 시스템은 차량 내부 승객의 쾌적한 환경을 유지하기 위해 실내온도를 제어하며, 주어진 범위 내에서 실내온도를 유지하기 위한 최소 소비전력을 계산해야 합니다. 초기 실내온도는 실외온도와 같으며, 에어컨 전원을 켜고 희망온도를 설정하면 실내온도가 매 분 1도씩 희망온도와 같아지는 방향으로 변화합니다. 에어컨의 소비전력은 희망온도와 실내온도의 상태에 따라 다르게 소비됩니다.

제한사항

• 온도 범위: -10 ≤ 실외온도 ≤ 40, -10 ≤ t1 < t2 ≤ 40
• 소비전력: 1 ≤ a, b ≤ 100
  • a: 희망온도와 실내온도가 다를 때의 1분당 소비전력
  • b: 희망온도와 실내온도가 같을 때의 1분당 소비전력
• 배열 조건:
  • onboard는 길이가 2 이상, 최대 1,000이며 0 또는 1로 구성
  • onboard[0]은 항상 0이고, 배열 내에 최소 하나 이상의 1이 존재

해결 방법

알고리즘: 동적 계획법(DP)

1. DP 배열 초기화:
   • dp[i][j]: i분에 실내온도가 j일 때 최소 소비전력을 저장.
   • 모든 값을 Infinity로 초기화하고, 초기 실내온도를 기준으로 dp[0][temperature] = 0 설정.
2. 온도 변환 및 범위 조정:
   • 온도가 음수를 포함하므로 계산을 간소화하기 위해 t1, t2, temperature에 10을 더하여 0 이상으로 변환.
3. DP 상태 갱신:
   • 매 분마다 승객 탑승 여부(onboard[i])와 실내온도를 확인하며 아래 상태를 갱신:
     • 실내온도가 증가하거나 감소할 때 소비전력 계산.
     • 희망온도와 실내온도가 같은 경우 소비전력 계산.
     • 실내온도가 실외온도로 복귀하는 경우를 고려.
4. 최소 소비전력 반환:
   • 최종 분(onboard.length)에서 모든 온도 상태 중 최소값을 반환.

시간 복잡도

• DP 배열 크기: O(n × m)
  • n: onboard 길이 (최대 1,000)
  • m: 온도 범위 (최대 51)
• 상태 갱신: O(3 × n × m) (온도 상승, 하강, 유지에 따른 갱신)
• 전체 시간 복잡도: O(n × m), 즉 최대 약 51,000번의 연산 수행.

구현 코드

function solution(temperature, t1, t2, a, b, onboard) {
  let dp = [];

  for (let i = 0; i <= 1000; ++i) {
    dp.push([]);
    for (let j = 0; j <= 51; ++j) {
      dp[i].push(Infinity);
    }
  }

  t1 += 10;
  t2 += 10;
  temperature += 10;
  dp[0][temperature] = 0;

  for (let i = 0; i < onboard.length; ++i) {
    for (let j = 0; j <= 50; ++j) {
      if (dp[i][j] === Infinity) {
        continue;
      }

      if (!onboard[i] || (j + 1 >= t1 && j + 1 <= t2)) {
        if (j < temperature) {
          dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1], dp[i][j]);
        }
        dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1], dp[i][j] + a);
      }
      if (!onboard[i] || (j - 1 >= t1 && j - 1 <= t2)) {
        if (j > temperature) {
          dp[i + 1][j - 1] = Math.min(dp[i + 1][j - 1], dp[i][j]);
        }
        dp[i + 1][j - 1] = Math.min(dp[i + 1][j - 1], dp[i][j] + a);
      }
      if (!onboard[i] || (j >= t1 && j <= t2)) {
        if (j === temperature) {
          dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j]);
        }
        dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + b);
      }
    }
  }

  return Math.min(...dp[onboard.length]);
}