-
[Python] 에어컨알고리즘/프로그래머스 2023. 7. 28. 09:28
https://school.programmers.co.kr/learn/courses/30/lessons/214289
- 코드
import math def solution(temperature, t1, t2, a, b, onboard): # 0으로 정규화 diff = temperature - t2 if temperature > t2 else t1 - temperature # 시간0에 대해 초기 비용으로 초기화 result = [[ 1000000 for i in range(diff+1) ]+[0]] last_passenger_index = 0 for i in range(1, len(onboard)): arr = [] for j in range(diff+2): temp = [result[i-1][j]+b] # 할수있는 행동(비용)은 온도유지(b), 온도 내리기(a), 온도올리기(0) if j == diff + 1: temp.append(result[i-1][j]) if j <= diff: temp.append(result[i-1][j+1] + a) if j > 0: temp.append(result[i-1][j-1]) min_cost = min(temp) # 시간i에 대해 승객에 탑승 중이고, 적정온도 범위 밖이라면. if onboard[i] == 1: last_passenger_index = i if j > 1: min_cost = 100000 # 100 * 1000 arr.append(min_cost) result.append(arr) return min(result[last_passenger_index])
- 문제 풀이
1. 0으로 정규화
문제에서 적정온도의 범위나 온도가 더 높거나 낮은것은 의미가 크게 없다.
적정온도가 0~10 일 때, 실외온도가 -10 이든 20 이든 필요한 최소 비용은 동일하다.
도달해야하는 온도를 0 으로하고, 도달해야하는 온도와 실외온도의 차이 diff를 구한다.
ex) 18~26 이 적정온도 이고, 실외 온도가 28 인 경우 > 도달해야하는 온도가 0 이고, 시작온도가 2 인 문제로 변환
2. 에어컨
1 과 같이 문제를 변환하였기 때문에, 시작온도는 항상 0 보다 크고, 에어컨을 키는 경우 항상 온도는 감소한다.
또한 에어컨을 끄는 경우 온도는 항상 증가한다.
에어컨의 경우 다음과 같다.
- 에어컨을 키고 온도를 감소시키는 경우(diff를 감소시키는 경우) 비용 a
- 에어컨을 키고 온도를 유지시키는 경우(diff유지) 비용 b
- 에어컨을 끄는 경우(diff 증가 or 유지) 비용 0
* 시작온도까지 온도(diff)가 변화하기 때문에, 시작온도와 일치한 시점에서는 더 이상 온도(diff)가 변화하지 않는다.
3. DP로 구현
해당 문제는 x 시점에 온도가 y 가 되도록 하는 최소비용 z 를 구하는 문제이다.
행을 시간으로 하고 열을 온도로 하는 리스트를 해당 지점의 최소비용으로 채워나가면 된다.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[2022 KAKAO TECH INTERNSHIP] 성격 유형 검사 (1) 2023.11.12 [2018 KAKAO BLIND RECRUITMENT] 셔틀버스 (0) 2023.08.11 [Python] 상담원 인원 (1) 2023.07.23 [2022 KAKAO BLIND RECRUITMENT] 주차 요금 계산 (0) 2022.08.24 [2022 KAKAO BLIND RECRUITMENT] k진수에서 소수 개수 구하기 (0) 2022.06.24