[C++ 2023 현대모비스 알고리즘 경진대회 예선] 에어컨

에어컨

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/214289

프로그래머스

프로그래머스에 있는 2023 현대모비스 알고리즘 경진대회 예선 문제이다.

문제제목과 같이 실내온도를 희망온도에 맞춰주는 문제이다. 이 때 희망온도를 유지하기 위한 최소한의 전력 사용량을 구해야 한다.

 

승객이 탑승했을 때 반드시 실내온도가 희망온도 사이여야 하는 조건이 있고, 최종적으로 최소 전력사용량을 구해야하기 때문에 dp로 접근했다. onboard길이, 변화가능한 온도 range로 이중 for문 만들고, i-1 시간에서 i 시간으로 갈 때 최소 전력사용가능한 시나리오를 min으로 선택해주었다.

승객이 탑승 중일 때 실내온도가 t1 보다 낮거나 t2 보다 높으면 실패한 경우이기 때문에 해당 값은 패쓰

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int dp[1005][55];
int mx = 2000000000;
int solution(int temperature, int t1, int t2, int a, int b, vector<int> onboard) {
    temperature += 10;
    t1 += 10;
    t2 += 10;
    for(int i = 0; i < 1005; i++) {
        for(int j = 0; j < 55; j++) {
            dp[i][j] = mx;
        }
    }
    int chk = 0;
    for(int i = 1; i < onboard.size(); i++) {
        if(onboard[i] == 1) {
            chk = i;
        }
    }
    dp[0][temperature] = 0;
    for(int i = 1; i < onboard.size(); i++) {
        for(int j = 0; j <= 50; j++) {
            if(onboard[i] == 1) {
                if(j < t1) {
                    continue;
                }
                if(j > t2) {
                    continue;
                }
            }
            if(j < temperature) {
                if(j == 0) {
                    dp[i][j] = min(dp[i-1][j]+b,dp[i-1][j+1]+a);
                    continue;
                }
                dp[i][j] = min({dp[i-1][j]+b,dp[i-1][j+1]+a,dp[i-1][j-1]});
            }
            else if(j > temperature){
                if(j == 0) {
                    dp[i][j] = min(dp[i-1][j]+b,dp[i-1][j+1]);
                    continue;
                }
                dp[i][j] = min({dp[i-1][j]+b,dp[i-1][j+1],dp[i-1][j-1]+a});
            }
            else {
                if(j == 0) {
                    dp[i][j] = min(dp[i-1][j],dp[i-1][j+1]);
                    continue;
                }
                dp[i][j] = min({dp[i-1][j],dp[i-1][j+1],dp[i-1][j-1]});
            }
        }
    }
    //cout << t1 << " " << t2 << "\n";
    for(int i = t1; i <= t2; i++) {
        if(mx > dp[chk][i]) {
            mx = dp[chk][i];
        }
        //cout << i << " "<< dp[chk][i] << "\n";
    }
    int answer = 0;
    answer = mx;
    return answer;
}