(백준/ C++) 1106 - 호텔 / 다이나믹 프로그래밍

 

" (백준/ C++) 1106 - 호텔 "

---

 

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

1106 - 호텔

 

이 문제는 냅색과 비슷하다.

다른 점이 있다면 중복으로 넣을 수 있는 점? 냅색 문제는 물건 하나 씩 넣는다. 

가장 간단해보이는 예제 입력1번을 보고 DFS를 이용하여 풀 수 있는 방법을 고민해봤다.  

" C명(12명)을 확보하면서 최소의 비용이 들어야 한다. 중복이 가능하다. " 

A: 5명/ 3비용, B: 1명/ 1비용
→ C명(12명) = AABB, ABBBBBBBB, BBBBBBBBBBBB 총 3개의 해답 중 가장 적은 비용이 든 조합이 해답이다. 

※ 점화식 생각 흐름  ※
→ [ C ] 에는 [ A ]가 몇명 들어갈까?, [ B ]가 몇명 들어갈까?
→ [ C - A ] 에는 [ A ]가 몇명 들어갈까?, [ B ]가 몇명 들어갈까?
→ [ C - B ] 에는 [ A ]가 몇명 들어갈까?, [ B ]가 몇명 들어갈까?

 

12명부터 시작해서 DFS로 0명이 되기까지 반복된다. 아래 그림에 있는 트리 처럼 이전의 해로 큰 해를 구할 수 있는 바텀업 방식( Bottom Up )으로 점화식을 만들었다. 

 

DP[C명] = 최소 비용 이므로, [ DFS(7) + cost[A] (3),  DFS(11) + cost[B] (1) ] 둘 중 작을 값이 DFS(12)의 해가 된다. cost [ index ]의 index는 각 도시의 인덱스가 해당되므로, for문을 돌려 도시 수 만큼 증가 시키며 인덱스를 증가 시키면 된다.

 

 

👩🏻‍💻 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include<cmath>
using namespace std;
int gN; // - 도시 개수
int gC; // - C명 늘이기 위해 형택이가 투자해야하는 돈의 최솟값의 C
int gCost[101]; // - 도시 홍보할 때 대는 비용
int gCCnt[101]; 
int DP[1001];

int DFS(int pCustomCnt)
{
	if (pCustomCnt <= 0)
	{
		return 0;
	}
	
	if (DP[pCustomCnt] > 0)
	{
		return DP[pCustomCnt];
	}

	int mMin = 1000 * 100; // C명 max:1000, 비용 max:100

	for (int i = 0; i < gN; ++i)
	{
		// ex) DFS(12[C명] - 5[고객 수]) + 3[비용] 
		// ex) DFS(12[C명] - 1[고객 수]) + 1[비용] 
		int mCost = DFS(pCustomCnt - gCCnt[i]) + gCost[i];
		mMin = min(mCost, mMin);
	}
	DP[pCustomCnt] = mMin;

	return DP[pCustomCnt];
}
int main(void)
{
	cin >> gC >> gN; 
	for (int i = 0; i < gN; ++i)
	{
		cin >> gCost[i] >> gCCnt[i]; 
	}

	cout << DFS(gC) << endl;
	return 0; 
}