에어컨 [Lv. 3] (C++)

프로그래머스

승객이 차량에 탑승 중일 때 항상 쾌적한 실내온도 (t1 ~ t2)를 유지 해야합니다.

항상 에어컨을 틀어놓는 것도 방법이 될 수 있지만 전기세를 아껴야 하기에

에어컨을 트는 최적의 방법을 찾아야 합니다.

따라서 우리는 승객이 탑승 중일 때 쾌적한 실내온도를 유지하는 방법 중 가장 적은 전기 사용량을 찾아야 합니다.

 

풀이 방법

경우의 수는 총 3개가 있습니다.

에어컨으로 온도를 낮추는 경우와 온도를 유지하는 경우, 그리고 에어컨을 끄는 경우

이 3개의 경우를 모두 탐색하여 최적의 전기 사용량을 찾으면 됩니다.

void dfs(vector<int>& onboard, int idx, int curTmpt, int cost)
{
	// 종료 후 비용 비교
    if (idx == onboard.size())
    {
        answer = min(answer, cost);
        return;
    }
    
    // 쾌적한 온도가 아니라면 return
    if (onboard[idx] == 1  && (curTmpt < _t1 || curTmpt > _t2))
        return;
    
    // 에어컨 끄기
        dfs(onboard, idx + 1, min(initTmpt, curTmpt + 1), cost);
    // 에어컨 유지
        dfs(onboard, idx + 1, curTmpt, cost + _b);
    // 에어컨 켜기'
        dfs(onboard, idx + 1, curTmpt - 1, cost + _a);
}

그럼 위처럼 dfs를 만들 수 있게 됩니다.

위의 코드로도 정답을 찾을 수는 있지만 속도 문제에 의해 해결은 안됩니다.

이 문제를 해결하기 위해서는 dynamic programming을 접목시킬 필요가 있습니다.

 

(5분에 21도)에 도달하기 위한 여러 경로가 있고 지금 모든 경로를 탐색중이라고 할 때

이미 최적의 경로가 나온 상황이라면 이후의 경로들은 탐색하지 않아도 상관없습니다.

( 우리는 경로를 탐색하는게 목적이 아니라 비용을 구하고 있기 때문,

  어차피 같은 위치에 같은 온도라면 이후의 경우의 수도 100% 동일하기에 중복 탐색하게 됨)

그렇기에 중간에 데이터를 저장하는 코드를 넣어주었습니다.

 

vector<vector<int>> dp(1001, vector<int>(51, 100000000));

if (dp[idx][curTmpt] <= cost )
    return;
dp[idx][curTmpt] = cost ;

최적의 경로를 찾은 상황이 아니라면 탐색 종료

 

 

 

위의 설명에는 경우의 수가 3개라고 이야기 했지만 사실 하나 더 있습니다.

실내 온도가 쾌적 온도 범위보다 낮을 때 [온도를 올리는 경우]입니다.

initTmpt = temperature ;
_t1 = t1 ;
_t2 = t2;
_a = a;
_b = b;

if (initTmpt < _t1)
    initTmpt = _t2 + (_t1 - initTmpt);

이 부분은 실외 온도를 쾌적 온도 범위보다 높게 바꿔주어 계산할 필요가 없게 했습니다.

구하는 것은 전기 소비량이기 때문에 상관없습니다.

 

전체 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> dp(1001, vector<int>(51, 100000000));
int initTmpt, _t1, _t2, _a, _b, answer = 10000000;

void dfs(vector<int>& onboard, int idx, int curTmpt, int cost)
{
    if (idx == onboard.size())
    {
        answer = min(answer, cost);
        return;
    }
    
    if (onboard[idx] == 1  && (curTmpt < _t1 || curTmpt > _t2))
        return;
    
    if (dp[idx][curTmpt] <= cost )
        return;

    dp[idx][curTmpt] = cost ;
    
    // 에어컨 끄기
        dfs(onboard, idx + 1, min(initTmpt, curTmpt + 1), cost);
    // 에어컨 유지
        dfs(onboard, idx + 1, curTmpt, cost + _b);
    // 에어컨 켜기'
        dfs(onboard, idx + 1, curTmpt - 1, cost + _a);
}

int solution(int temperature, int t1, int t2, int a, int b, vector<int> onboard) {
    initTmpt = temperature ;
    _t1 = t1 ;
    _t2 = t2;
    _a = a;
    _b = b;
    
    if (initTmpt < _t1)
        initTmpt = _t2 + (_t1 - initTmpt);
    
    dfs(onboard, 0, initTmpt, 0);

    return answer;
}