백준 1106. 호텔 (DP)

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

1106번: 호텔

 

전형적인 dp 문제이다. 

 

1. 특징

이 문제의 점화식이 백준 14501.퇴사 문제와 비슷하다.

https://todaywithhaeul.tistory.com/159

 

나는 우선 dp 테이블을 정의했다. 1) d[i]: i원을 쓸 때 늘릴 수 있는 인원의 최댓값 or 2) d[i]: 고객수를 i명으로 늘릴때 비용의 최솟값.

나는 2번으로 정의했다. (1번 풀이로 하고 싶다면, https://ongveloper.tistory.com/323)

 

그리고 점화식을 세웠다. d[i] = min(d[i], d[i - arr[j][1]] +  arr[j][0]);

d[현재 고객수] = d[현재고객수 - 도시별 늘릴 수 있는 고객수] + 도시별 비용

 

2. 삽질 포인트

1) 이 문제의 조건은 고객을 적어도 c명 늘이기 위해 투자하는 돈의 최솟값을 구하는 것이다. c명 늘이는 것보다 c+1 명 늘이는 것의 비용이 작다면 c+1의 비용을 출력해야 한다.  c가 1000명 이하의 자연수 이다. 그리고 홍보할 때 드는 비용은 100이하의 자연수이다. 따라서 d[1101]로 선언해야한다. 이 부분을 이해를 잘못해서 범위 설정에 따른 오류가 발생했다. 

int d[1101]; // i명 늘릴 때 비용의 최솟값
int ans = INT_MAX;
for(int i = 0; i < 101; i++)
{
    if(d[c+i] != 0)
        ans = min(ans, d[c+i]);
}

cout << ans;

 

2) min함수를 사용해서, d[i]를 갱신해줬는데, 처음 d의 모든 값을 0으로 초기화해서 오류가 발생했다. 

처음의 d[i]는 자기 자신의 비용으로 초기화해야한다. 

또한, 비용이 겹치는 값이 들어올 수 있다. 예를 들어 4명을 늘리는데 3원이 드는 도시와, 4명을 늘리는데 8원이 드는 도시가 있다면 d[4] = 3으로 초기화 해야 한다. 

for(int i =0; i < n; i++)
{
    if(d[a[i][1]] != 0) d[a[i][1]] = min(a[i][0], d[a[i][1]]);
    else d[a[i][1]] = a[i][0];
}

 

마지막으로, 고객수를 i명으로 늘릴 수 없는 경우, d[i] = 0으로 유지해줘야한다. 

if(i-a[j][1]>=0 && d[i-a[j][1]] != 0) //d[i-a[j][1]] != 0 조건이 필요하다
{
    if(d[i] == 0) d[i] = d[i-a[j][1]]+ a[j][0];
    else d[i] = min(d[i], d[i-a[j][1]]+ a[j][0]);

}

 

3. 코드

#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;

int c, n;
int d[1101]; // i명 늘릴 때 비용의 최솟값
int a[1002][2]; 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> c >> n;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            cin >> a[i][j];        
        }
    }

    for(int i =0; i < n; i++)
    {
        if(d[a[i][1]] != 0) d[a[i][1]] = min(a[i][0], d[a[i][1]]);
        else d[a[i][1]] = a[i][0];
    }

    for(int i = 1; i <= 1101; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(i-a[j][1]>=0 && d[i-a[j][1]] != 0)
            {
                if(d[i] == 0) d[i] = d[i-a[j][1]]+ a[j][0];
                else d[i] = min(d[i], d[i-a[j][1]]+ a[j][0]);
                
            }
        }
    }

    int ans = INT_MAX;
    for(int i = 0; i < 101; i++)
    {
        if(d[c+i] != 0)
            ans = min(ans, d[c+i]);
    }

    cout << ans;

}