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

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

프로그래머스

 

2024.02.05 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

[문제 조건]

• 차내는 승객이 탑승해 있는 동안 t1~t2 (t1이상 t2이하)의 온도를 유지해야 한다.
• 온도는 에어컨을 통해 조절할 수 있다.
• 실내온도와 희망온도가 다르다면 1분 뒤 실내온도는 희망온도와 같아지는 방향으로 1도 상승 또는 하강한다.
• 실내온도와 희망온도가 같다면 에어컨이 켜져있는 동안 실내온도가 변하지 않는다.
• 에어컨의 전원을 끄면 실내온도가 실외온도와 같아지는 방향으로 매 분 1도 상승 또는 하강한다. (두 온도가 같다면 변화 X)
• 에어컨의 희망온도와 실내온도가 다르다면 매 분 전력을 a만큼 소비하고 같다면 b만큼 소비한다.
• 에어컨을 끄면 전력을 소비하지 않는다.
• 에어컨을 끄고 키는데 필요한 시간과 전력은 0이라고 가정한다.
• 승객이 탐승 중일 때 온도를 t1~t2 사이로 유지하면서 에어컨의 소비 전력을 최소화할 때의 총 소비 전력을 구해야 한다.

 

이 문제에서 희망 온도는 함정입니다.

현재 실내 온도가 10도이고 1분 뒤 온도를 1 낮추고 싶다면 10보다 낮은 수가 희망온도이기만 하면 1도를 낮출 수 있기 때문에 우리는 매 순간 정확한 희망온도를 구할 필요가 없습니다.

 

그리고 가장 중요한 사실은 1분에 1도씩만 변할 수 있다는 점입니다.

 

i분의 온도를 j라고 하면, i+1의 온도는 j-1 또는 j 또는 j+1만 가능합니다.

 

따라서 우리는 가능한 경우의 수를 한정할 수 있고 이를 통해 점화식을 세울 수 있습니다.

 

결국 이 문제는 DP로 해결이 가능해졌습니다.

 

DP 로직을 구현하기 전에 온도 범위를 조정할 필요가 있습니다.

이 문제에서 온도 정보들은 -10~40 도 사이로 주어지는데 배열의 인덱스는 음수일 수 없으므로 전부 0이상으로 보정해야 합니다.

이를 위해 온도 정보인 temperature, t1, t2에 각각 10을 더해줘서 온도 범위가 0~50이 되도록 변경합니다.

 

이제 DP 배열을 2차원 배열로 생성합니다.

dp[i][j]를 i분일 때 j도가 되도록 하는 최소 소비 전력으로 간주합니다.

 

현재 온도 j를 만들기 위해서는 총 3가지 경우의 수가 존재합니다.

1. dp[i-1][j-1] 에서 1도를 증가시킨 경우
2. dp[i-1][j+1] 에서 1도를 감소시킨 경우
3. dp[i-1][j] 에서 온도를 유지한 경우

그리고 이 3가지 경우는 외부온도에 따라 각각 계산이 필요합니다.

1. 실내온도가 외부온도보다 높은 경우일 때 위의 3가지 경우 계산
   • dp[i][j] = min(dp[i][j], dp[i-1][j-1] + a)
   • dp[i][j] = min(dp[i][j], dp[i-1][j+1])
   • dp[i][j] = min(dp[i][j], dp[i-1][j] + b)
2. 실내온도가 외부온도보다 낮은 경우일 때 위의 3가지 경우 계산
   • dp[i][j] = min(dp[i][j], dp[i-1][j-1])
   • dp[i][j] = min(dp[i][j], dp[i-1][j+1] + a)
   • dp[i][j] = min(dp[i][j], dp[i-1][j] + b)
3. 실내온도가 외부온도보다 같은 경우일 때 위의 3가지 경우 계산
   • dp[i][j] = min(dp[i][j], dp[i-1][j-1])
   • dp[i][j] = min(dp[i][j], dp[i-1][j+1])
   • dp[i][j] = min(dp[i][j], dp[i-1][j])

 

이렇게 dp 배열을 갱신시켜 나가면 됩니다.

 

배열이 다 채워지면 dp[onboard.count-1]에서 가장 작은 값이 최소 소비전력에 해당됩니다.

 

 

 

풀이

solution 함수 구현

fileprivate func solution(_ temperature:Int, _ t1:Int, _ t2:Int, _ a:Int, _ b:Int, _ onboard:[Int]) -> Int {
  let temperature = temperature + 10
  let t1 = t1 + 10
  let t2 = t2 + 10
  let n = onboard.count
  
  var dp = Array(repeating: Array(repeating: 1000*100, count: 52), count: n) // dp[i][j]는 i분일 때 j도가 되도록 하는 최소 소비 전력
  
  dp[0][temperature] = 0
  
  for i in 1..<n {
    for j in 0..<dp[0].count-1 {
      
      if onboard[i] == 1 && (j < t1 || j > t2) {
        continue
      }
      
      if j > temperature {
        // j-1도를 j로 높이는 경우 -> 에어컨 on
        if j-1 >= 0 {
          dp[i][j] = min(dp[i][j], dp[i-1][j-1] + a)
        }
        
        // j+1도를 j로 낮추는 경우 -> 에어컨 off
        dp[i][j] = min(dp[i][j], dp[i-1][j+1])
        
        // j도 유지 -> 에어컨 on
        dp[i][j] = min(dp[i][j], dp[i-1][j] + b)
      } else if j < temperature {
        // j-1도를 j로 높이는 경우 -> 에어컨 off
        if j-1 >= 0 {
          dp[i][j] = min(dp[i][j], dp[i-1][j-1])
        }
        
        // j+1도를 j로 낮추는 경우 -> 에어컨 on
        dp[i][j] = min(dp[i][j], dp[i-1][j+1] + a)
        
        // j도 유지 -> 에어컨 on
        dp[i][j] = min(dp[i][j], dp[i-1][j] + b)
      } else {
        // j-1도를 j로 높이는 경우 -> 에어컨 off
        if j-1 >= 0 {
          dp[i][j] = min(dp[i][j], dp[i-1][j-1])
        }
        
        // j+1도를 j로 낮추는 경우 -> 에어컨 off
        dp[i][j] = min(dp[i][j], dp[i-1][j+1])
        
        // j도 유지 -> 에어컨 off
        dp[i][j] = min(dp[i][j], dp[i-1][j])
      }
    }
  }

  return dp[n-1].min()!
}

 

앞서 설명한 경우의 수들을 전부 검사하면 2중 for문을 통해 dp배열을 채워 나갑니다.

온도 범위가 0~50도 이기 때문에 dp 배열의 열 개수를 52로 설정했습니다.

 

dp[0][temperature]는 처음 시작 온도이기 때문에 소비전력을 0으로 지정합니다.

 

onboard[i]가 1이고 j < t1 || j > t2 라면 승객이 탔는데 주어진 온도 범위를 벗어난 상황이기 때문에 계산을 하지 않고 넘어갑니다.

 

dp[i][j-1] 에 접근하는 경우 j가 1보다 작다면 index out of range가 발생하기 때문에 if문으로 j-1>=0 인지 검사합니다.

 

 

 

마무리

개인적으로 dp문제가 어렵게 느껴집니다.

점화식을 찾는 과정이 어려운데 특히 이번 문제는 외부온도에 따라 경우의 수가 증가하여 dp 배열을 업데이트 하는 케이스가 많아서 특히 쉽지 않았습니다. 이 부분을 다른 분들 답안 힌트에서 참고했습니다.

 

희망온도에 낚이지 않고 침착하게 1분 전 온도에서 1도 또는 0도 변한 온도만 만들 수 있다는 점을 파악해야 했습니다.

 

이 문제를 끝으로 현재(2/5) 기준으로 프로그래머스 Level 3 문제를 다 풀어보고 풀이방법을 블로그에 올리는 목표를 완수했습니다..!!

추후에 문제가 더 추가되면 계속 풀어볼 예정입니다!

지금까지 스스로 푼 문제도 있지만 아이디어가 정말 생각나지 않아서 다른 분들이 올려주신 힌트를 참고한 문제도 많이 있었습니다.

이제는 Level 3 문제들을 다시 풀어보면서 되돌아보려고 합니다.