[ 백준 BOJ ] 1106번 - 호텔 (C++)

https://www.acmicpc.net/problem/1106

 

생각 흐름

• 인원/비용을 계산한 다음 큰 순으로 정렬하고 답 구하기 -> 예제 1번 부터 성립 X
• 최솟값을 구하는 문제이므로 DP 점화식 생각해보기로 결정
  • dp[i] = max(dp[i], dp[i+인원] + 인원에 따른 비용)와 같이 세워보니 답이 나올 거 같았다.
• 이때 주의할 점으로는 딱 C의 값을 맞추는 게 아니므로 dp 배열 중 C값 이상 인덱스 중에서 최솟값을 찾아줘야 한다.

 

#include <iostream>
#include <vector>
#include <memory.h>
#include <cmath>

using namespace std;

int C, N;
pair<int, int> p[20];
int dp[3000];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>C>>N;
    
    for(int i = 0; i<N; i++){
        int a, b;
        cin>>a>>b;
        
        p[i] = {a,b};
    }
    
    for(int i = 1; i<3000; i++){
        dp[i]=987654321;
    }
    dp[0] = 0;
    
    for(int i = 0; i<=C; i++){
        if(dp[i] == 987654321) continue;
        
        for(int j = 0; j<N; j++){
            dp[i+p[j].second] = min(dp[i+p[j].second], dp[i]+p[j].first);
        }
    }
    
    int answer = 987654321;
    for(int i = C; i<C+101; i++){
            answer = min(answer, dp[i]);
    }
    
    cout<<answer<<endl;
    
    return 0;
}