문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/214289
2023 현대 모비스 알고리즘 대회 예선에서 올라온 문제다.
프로그래머스에 카카오 기출 말고 다른 기업 것을 풀어보는 건 처음이었는데,
확실히 유형이 다르다는 것을 느꼈다.
문제가 나온 지 얼마 안 돼서 푼 사람이 70명 남짓밖에 되지 않았다.
그래서 참고할만한 인터넷 글은 없었는데, 다행히 질문 글에 해설 글을 참고하여 풀 수 있었다.
그렇게 여차저차 2일 만에 문제를 해결했다.
문제 핵심 및 풀이
희망 온도
마치 중요한 것처럼 적혀있지만, 희망온도라는 키워드에 속지 않도록 해야 한다.
문제 설명에서 보면
"희망 온도는 에어컨의 전원이 켜져 있는 동안 원하는 값을 변경할 수 있습니다."
라고 되어있다.
이는 희망온도가 고정이 아니라는 뜻이다.
즉, 이득이 되는 방향으로 언제든 바꿔 되기 때문에 고려 대상이 아니다.
희망온도에 집중해 버리면 문제가 어려워진다.
동적 계획법(Dynamic Programming) 임을 파악
해당 문제가 그리디 유형이지 않을까 생각할 수도 있다.
하지만 해당 시점에서 가장 이득이 되는 선택을 하더라도, 최종적인 답(최소 전력)이 되지 않을 수 있다.
여기서 문제 유형을 얻을 수 있는 힌트는, 1분마다 변할 수 있는 온도가 한정되어 있다는 것이다.
예를 들어서 현재 온도가 27도라면,
다음 온도는 28도, 27도, 26도 중 하나이다.
이를 역으로 생각해 보자.
현재 온도가 27도라면 이전 온도는 몇 도였을까?
적어도 후보를 3가지(28,27,26)로 특정 지을 수 있다.
이를 일반화해 보자.
현재 i분이고, 온도가 j인 것을 ( i , j )라고 나타내자.
이때 이 온도 j는 어디서부터 왔을까?
당연히 ( i-1 , j-1 ) , ( i-1 , j ) , ( i-1, j+1 ) 이 3개 중 하나이다.
여기서 이제
DP [i][j] = k : 현재 시간이 i분이고 j도 일 때의 최소 전력은 k라고 해보자.
그렇다면
DP [i][j] = Min(DP [i-1][j-1], DP [i-1][j], DP [i-1][j+1])이 된다.
이렇듯 이전의 결과를 통해 현재의 결과를 구할 수 있으므로,
해당 문제는 DP로 접근 가능하다는 것을 알 수 있다.
가능한 행동의 선택지
이제부터는 세분화하는 것이 중요하다.
현재 온도 J를 만들기 위해서 할 수 있는 선택지는 다음과 같다.
여기서 가정은 외부 온도 > t2이다.
그래서 에어컨을 끄면 1도가 상승하고, 에어컨을 켜면 1도가 하강한다.(내부온도와 외부온도가 다를 시)
1. 이전 온도 J-1에서 에어컨 OFF → 비용 0
2. 이전 온도 J에서 에어컨 ON (희망 온도를 J로 하고 유지) → 비용 b
3. 이전 온도 J+1에서 에어컨 ON → 비용 a
4. 이전 온도 J에서 에어컨 OFF ( J == 외부온도 일 때 ) → 비용 0
4번째 경우는 특수한 경우로, 이는 온도는 외부 온도 초과로는 올라가지 않기 때문이다.
만약 외부 온도 < t1이라면 위 그림을 반대로 생각하면 된다.
그렇다면 온도는 외부 온도 미만으로는 내려가지 않을 것이다.
범위 설정
이 문제에서 DP를 사용하기 위해서는 2차원 배열을 써야 하는데,
온도의 범위가 -10 ~ 40 이어서, 음수가 들어간다.
이는 임의의 수를 더해줘서 음수를 제거해 주면 된다.
필자 같은 경우는 10이 아닌 15를 더해줬는데, 만약 10으로 하면 0 ~ 50으로 잘못하면 -1이 될 수 있기 때문이다.
두 번째로 중요한 범위 설정은 DP를 돌릴 때 범위의 설정이다.
실외온도로부터 가능한 최대/최소 온도의 범위는 어떻게 정해야 할까?
(실외온도 > t2)라면 가능한 최대온도는 실외온도이다.
실외온도를 넘길 수는 없기 때문이다.
그렇다면 최저 온도는 어떨까?
이때 최저 온도는 쾌적 실내 온도의 최소 값인 t1이 된다.
어차피 우리 목표는 실내온도에 맞추는 것이기에 해당 값을 넘을 이유가 전혀 없다.
즉 최종 정리하자면
실외 온도 > t2 인 경우의 범위 : t1 ~ 실외온도
실외온도 < t1인 경우의 범위 : 실외온도 ~ t2
마지막으로 고려해줘야 하는 것은 승객이 탑승해 있을 때이다.
승객이 탑승해 있을 때는 항상 쾌적한 온도여야 한다.
즉, onboard [i]가 1이라면 온도가 t1 ~ t2인 것만 계산을 해야 한다.
이제 위에서 제시한 아이디어들을 이용하여 문제를 풀면 된다.
아래에 코드를 통해 구현해 보겠다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <algorithm>
#define MAX 99999999 // min에 걸리지 않을만큼 큰 값
using namespace std;
int solution(int temperature, int t1, int t2, int a, int b, vector<int> onboard) {
int dp[1001][55]; // 온도 인덱스를 넉넉히
int answer = MAX;
int unit; // 외부온도로 가는 단위
int start,end; // 탐색 시작 ~ 종료 범위
fill(&dp[0][0],&dp[1000][55],MAX); // dp 배열을 MAX로 초기화
// 15씩 더해서 음수 없애줌
t1 += 15;
t2 += 15;
temperature += 15;
// t1보다 작은 경우 -> temperature = 최솟값
if(temperature < t1){
unit = -1;
start = temperature;
end = t2;
}
// t2보다 큰 경우 -> temperature = 최댓값
else{
unit = 1;
start = t1;
end = temperature;
}
// 초기 dp 값 세팅
dp[0][temperature] = 0;
dp[0][temperature-unit] = a;
for(int i = 1; i < onboard.size(); i++){
for(int j = start; j <= end; j++){
// 승객이 있을때는 온도가 t1 ~ t2 사이여야 함
if(onboard[i] == 1 && (j < t1 || j > t2)) continue;
// 온도가 외부온도와 같을 때(특수한 경우)
if(j == temperature){
// 1. j 온도에서 OFF 2. j-unit 온도에서 OFF
dp[i][j] = min(dp[i-1][j],dp[i-1][j-unit]);
}
else{
// 1.j 온도에서 ON으로 유지 2.j+unit 온도에서 ON
dp[i][j] = min(dp[i-1][j]+b,dp[i-1][j+unit]+a);
// 3.j-unit 온도에서 OFF
dp[i][j] = min(dp[i][j],dp[i-1][j-unit]);
}
// 마지막일 경우 해당 값으로 답을 찾음
if(i == onboard.size()-1) answer = min(answer,dp[i][j]);
}
}
return answer;
}↑
Java 구현 코드
↓
class Solution {
static final int MAX = 9999999; // Min 에 걸리지 않을 정도로 큰 값
public int solution(int temperature, int t1, int t2, int a, int b, int[] onboard) {
int answer = MAX;
// dp[분][온도] 를 넉넉하게 설정
int[][] dp = new int[1001][60];
// 외부 온도에 가만히 뒀을 때 더해져야하는 기본 단위 설정
int unit =(temperature < t1)? -1 : 1;
// dp = MAX로 초기화
for(int i = 0; i <= 1000; i++)
for(int j = 0; j < 60; j++) dp[i][j] = MAX;
// 모든 온도에 15를 더함
t1 += 15;
t2 += 15;
temperature += 15;
// 초기 dp 값 초기화
dp[0][temperature] = 0;
dp[0][temperature-unit] = a;
// 1분부터 시작
for(int i = 1; i < onboard.length; i++){
// 이것도 마찬가지로 temperature ~ t2 인지,
// t1 ~ temperature 인지 설정
int start = (unit == 1)? t1 : temperature;
int end = (unit == 1)? temperature : t2;
for(int j = start; j <= end; j++){
// 승객이 탑승 중인데 t1 ~ t2 사이가 아닌 온도라면 패스
if(onboard[i] == 1 && (t1 > j || j > t2)) continue;
// 현재 j 온도가 외부 온도와 같을 경우(특수한 상황)
if(j == temperature){
// 1. j 온도에서 OFF 2. j-unit 온도에서 OFF
dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-unit]);
}
else{
// 1. j-unit 온도에서 OFF 2. j+unit 온도에서 ON
dp[i][j] = Math.min(dp[i-1][j-unit],dp[i-1][j+unit]+a);
// 3. j 온도에서 ON으로 유지
dp[i][j] = Math.min(dp[i][j],dp[i-1][j]+b);
}
// 마지막까지 도달한 경우 그걸로 답을 도출
if(i == onboard.length-1) answer = Math.min(answer,dp[i][j]);
}
}
return answer;
}
}↑
시행착오
오랜만에 엄청나게 오래 풀었던 문제 같다.
인터넷에는 풀이가 없는 문제였지만 질문하기 게시판에 해설을 올려주신 분 덕분에 많은 힌트가 됐다.
DP 유형을 오랜만에 풀어봐서 그런지 많이 헤맸다.
아니 심하게 헤맸다.
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me