[백준 1082] 방 번호

• 문제 : 1082 방 번호
• 유형 : dfs, 메모이제이션, dp
• 풀이 : 최대 2^50개 숫자를 선택하야 하는 경우가 있기 때문에 메모이제이션을 통한 시간 단축이 필수였고 50자리 숫자를 저장하기 위해 문자열로 관리하였다. 깊이(인덱스)와 남은 비용을 가지는 map을 이용하여 DP 테이블을 설정하였고 해당 인덱스에서 만들 수 있는 최대 값을 저장해두었다. 문자열 간의 비교를 따로 함수로 정의해주었고 길이를 먼저 비교하고 길이가 같으면 처음부터 크기를 비교하여 반환해주었다. 만약 0으로 시작하는 숫자가 있으면 무조건 반대 문자열을 리턴해주었다.

• 코드

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
int n, arr[11], M;
map<pair<int, int>, string>m;
int ans = 0;

string MAX(string a, string b) {
	if (a[0] == '0') return b;
	else if (b[0] == '0') return a;

	if (a.size() > b.size()) return a;
	else if (a.size() < b.size()) return b;
	else {
		if (a.compare(b) < 0) return b;
		else return a;
	}
}

string dfs(int d, int c) {
	if (c < M) { // 남은 금액이 최소비용 보다 작으면
		return "";
	}

	
	if (m.count({ d, c }) != 0) return m[{d, c}];
	string& ret = m[{d, c}];

	for (int i = 0; i < n; i++) {
		if (c - arr[i] >= 0) {
			ret = MAX(ret, dfs(d + 1, c - arr[i]) + (char)(i + '0'));
		}
	}

	return ret;
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	int c;
	cin >> c;
	M = *min_element(arr, arr + n);
	
	
	string ans = dfs(0, c);
	if (ans.size() == 0) ans = "0";
	cout << ans;


	return 0;
}