백준 1106 c++ "호텔" -PlusUltraCode-

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

 

[필자 사고]

동적 프로그래밍 문제이면서 배낭 문제이다.

이번에 필자는 탑다운 방식으로 문제를 해결해 나갔따.

탑다운 방식은 뮤탈리스크 문제를 통해 배웠었다. 

 

필자가 푼 사고 과정은 다음과 같다.

dp[N] << 사람수를 의미하고 

매번 시행 마다 N-person 을 해줘서 처음 0보다 작거나 같을 때 순간까지 구해주는 방식으로 해결했따.

 

[코드 해설]

 

• 입력 처리 (Input 함수)
  Input() 함수는 호텔 홍보 목표 고객 수(C)와 홍보할 수 있는 도시의 개수(N)를 입력받는다. 이후 각 도시에서 홍보할 때 필요한 비용과, 그 비용을 지불했을 때 얻을 수 있는 고객 수를 입력받아 벡터 arr에 저장한다. 입력이 완료된 후 동적 프로그래밍을 위한 배열인 dp를 목표 고객 수 만큼의 크기로 초기화하여 준비한다
• 재귀적 동적 프로그래밍을 이용한 최소 비용 계산 (Solution 함수)
  Solution() 함수는 동적 프로그래밍을 재귀적으로 활용하여 최소 비용을 계산한다. 이 함수는 고객 수를 매개변수로 받아, 현재 상태(남은 고객 수)에 대한 최소 비용을 메모이제이션을 통해 중복 계산 없이 효율적으로 계산한다. 매 호출마다 모든 도시를 순회하며 각 도시에서 얻을 수 있는 고객 수를 기준으로 재귀적으로 호출된 최소 비용을 비교하고, 가장 작은 비용을 찾아 저장하여 반환한다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define MAX 99999999
using namespace std;
typedef pair<int, int> Node;
int C, N;

vector<int> dp;
vector<Node> arr;

void Input() {
	cin >> C >> N;
	dp.resize(C + 1, MAX);
	arr.resize(N + 1);
	for (int i = 1; i <= N; i++) {
		int s, e;
		cin >> s >> e;
		arr[i] = {s,e};
	}
}

int Solution(int numIdx) {

	if (numIdx <= 0)return 0;
	
	int& ret = dp[numIdx];
	if (ret != MAX)return ret;
	
	for (int i = 1; i < arr.size(); i++) {
		int cost = arr[i].first;
		int person = arr[i].second;

		ret = min(ret, Solution(numIdx - person) + cost);
	}
	return ret;
}

int main(void) {
	Input();
	cout << Solution(C) << '\n';
}