[프로그래머스/C++] 에어컨 (feat.Python)

 

 

문제

문제 설명

 

풀이

 

[풀이]

 

BFS나 DFS로 계속 온도를 바꿔 가면서 풀기에는 각 경우마다 3개의 경우가 나오기 때문에 속도가 오래 걸릴 것이라는 생각이 들어서 DP로 풀었다.

 

DP로 풀 경우 이전 탑승 중인 시간에서 현재 탑승 중인 시간으로 변할 때, 특정 온도의 전력값이 최소인 경우를 구하면 된다.

 

희망온도를 몇으로 할 지 특별히 신경쓰지 않아도 되는 이유는 경우를 3개로 나눠서 구분할 수 있기 때문이다.

(그러므로 구체적인 희망온도를 설정할 필요 X)

 

1. 에어컨을 일정온도로 유지하는데 사용

2. 에어컨의 온도를 쾌적한 방향으로 유지 => 더우면 시원하게, 추우면 따뜻하게

3. 에어컨을 끄기

​

이 때 주의해야하는 점은 현재 온도가 유지되는 경우가 실외 온도에 도달하는 경우도 있다는 점

​

​

[아이디어 정리]

1. 실외 온도가 쾌적한 온도 범위보다 높은지, 낮은지 구분한다.
2. 현재 온도에서 전력소비의 최소값은 이전 승객 탑승 시간 중에서 에어컨을 키는 경우(온도유지), 에어컨을 키는 경우(온도가 쾌적한 방향), 에어컨을 키지 않는 경우 3개 중 최솟값이다.
3. 위 과정을 반복해 마지막에서 에어컨의 소비전력이 최소인 값을 return한다.

 

 

Code [C++]

 

 

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

using namespace std;

int ret1,ret2;
bool FuncTF(int tem)
{
    if (ret1<=tem&&tem<=ret2)
    {
        return true;
    }
    return false;
}
int minC(int a, int b)
{
    if (a<b)
        return a;
    else
        return b;
}

int solution(int temperature, int t1, int t2, int a, int b, vector<int> onboard) {
    int dT;
    bool flag=false;
    int boardSize = onboard.size(); //시간
    vector<vector<int>> DP(boardSize, vector<int>(51,10000000)); // y가 시간, x가 온도
    t1+=10; t2+=10; temperature+=10;
    ret1=t1; ret2=t2;
    if (temperature<t1)
    {
        dT=1;
    }
    else if (temperature>t2)
    {
        dT=-1;
    }
    else
    {
        //에너지 소모 X
        return 0;
    }
    DP[0][temperature]=0;
    for (int i=1; i<DP.size(); i++)
    {
        for (int j = 0; j<DP[0].size(); j++)
        {
            // 아래 식은 현재 승객이 탑승했을 때, 즉 onboard가 1이면 j가 내가 원하는 범위여야함
            if((onboard[i]==1 && t1<=j && j<=t2) || onboard[i]==0)
            {
                // 온도변화 X
                DP[i][j]=minC(DP[i-1][j]+b,DP[i][j]);
                // 온도 변화가 좋은쪽으로 변화, 이전 상태가 더 좋았으므로 -dT에서 변화
                if (0<=j-dT&& j-dT<51)
                {
                    DP[i][j]=minC(DP[i-1][j-dT]+a,DP[i][j]);    
                }
                // 온도가 안 좋은 방향으로 변화 
                if (0<=j+dT&& j+dT<51)
                {
                    // 현재 온도가 실외온도보다 더 나빠지는 경우는 없어야 함
                    if (dT==-1) //실외 온도가 높은 경우
                    {   
                        if (j<=temperature)
                        {
                            DP[i][j]=minC(DP[i-1][j+dT],DP[i][j]);
                        }
                    }
                    else // 실외 온도가 낮은 경우
                    {
                        if (j>=temperature)
                        {
                            DP[i][j]=minC(DP[i-1][j+dT],DP[i][j]);
                        }
                    }
                }
                if (j==temperature) // 만약 실외온도랑 같다면 변화x
                {
                    DP[i][j]=minC(DP[i-1][j],DP[i][j]);
                }
            }
        }   
    }
    int answer = 10000000;
    for (int i=0; i<DP[0].size(); i++)
    {
        answer=minC(answer,DP[DP.size()-1][i]);
    }
    return answer;
}

 

 

 

Code [Python]

 

 

 

def solution(temperature, t1, t2, a, b, onboard):
    answer = 0
    temperature+=10
    t1+=10
    t2+=10
    dt=0
    maxn=0
    # dt를 더해주면 에어컨을 쓴다는 것
    if temperature<t1: # 실외가 추울때 
        dt=1
    elif temperature>t2: # 실외가 더울때
        dt=-1
    else:
        return 0;
    dp=[[100000000]*51 for _ in range(len(onboard))]
    dp[0][temperature]=0
    for i in range(1,len(dp)):
        for j in range(len(dp[0])):
            if (onboard[i]==1 and t1<=j<=t2) or onboard[i]==0:
                dp[i][j]=min(dp[i][j],dp[i-1][j]+b) # 온도유지
                if 0<=j-dt<51: # 전력 소모
                    dp[i][j]=min(dp[i][j],dp[i-1][j-dt]+a)
                if 0<=j+dt<51: # 전력 소모 x
                    if dt==1:
                        if j>=temperature:
                            dp[i][j]=min(dp[i][j],dp[i-1][j+dt])
                    else:
                         if j<=temperature:
                            dp[i][j]=min(dp[i][j],dp[i-1][j+dt])
                if (j==temperature):
                    dp[i][j]=min(dp[i][j],dp[i-1][j])
    answer = min(dp[i])
    return answer

---

 

 

C++로 푸는데

처음에 cout으로 잘 출력되는지 확인하려고 적어둔 코드 때문에 자꾸 test case 3개가 틀렸다;;

결국 python으로 옮겨서 다시 풀고 정답처리가 되길래, python코드랑 비교하면서 겨우 찾았다...

한번에 잘 풀자 제발 ㅠㅠㅠㅠ

 

프로그래머스