[백준] 1301-비즈 공예(C++)

문제링크:www.acmicpc.net/problem/1301

1301번: 비즈 공예

 

문제의 핵심 조건은 N은 3보다 크거나 같고, 5보다 작거나 같다. 둘째 줄부터 N개의 줄에 각각의 구슬이 총 몇 개 있는 지주어진다. 첫째 줄에는 1번 구슬, 둘째 줄에는 2번 구슬, 이런 형식이다. 각각의 구슬은 10개보다 작거나 같은 자연수이다. 그리고, 구슬의 총 개수의 합은 35를 넘지 않는다.

 

수의 범위가 작기때문에 긴 차원의 배열을 만들어도 된다는 것을 알게되었습니다.

모든 경우를 고려해주는 것으로 생각을 가지게 되었습니다.

 

 무려 7차원 배열입니다.

dp[dp[arr[1]][arr[2]][arr[3]][arr[4]][arr[5]][prefer][current] = 5종류의 구슬이 arr[i] 개씩 남아있고, 이전 구슬이 prefer, 현재 선택한 구슬이 current일때의 경우의 수의 합입니다.

 

 

그렇다면 재귀식은 아래 처럼 구현할 수 있습니다.

long long solved(int prefer, int current,int cnt) {
	if (cnt == sum) {
		return 1;
	}
	
	long long &ret = dp[arr[1]][arr[2]][arr[3]][arr[4]][arr[5]][prefer][current];
	if (ret != -1)
		return ret;
	ret = 0;
	for (int i = 1; i <= n; i++) {
		if (prefer != i && current != i && arr[i]) {
			arr[i]--;
			ret += solved(current, i, cnt+1);
			arr[i]++;
		}

	}

	return ret;
}

 

 

아래는 전체 정답 코드입니다.

#include <iostream>
#include <cstring>
using namespace std;

int n = 0, result = 0,sum=0;
int arr[6] = { 0, };
long long dp[11][11][11][11][11][6][6] = { 0, };

long long solved(int prefer, int current,int cnt) {
	if (cnt == sum) {
		return 1;
	}
	
	long long &ret = dp[arr[1]][arr[2]][arr[3]][arr[4]][arr[5]][prefer][current];
	if (ret != -1)
		return ret;
	ret = 0;
	for (int i = 1; i <= n; i++) {
		if (prefer != i && current != i && arr[i]) {
			arr[i]--;
			ret += solved(current, i, cnt+1);
			arr[i]++;
		}

	}

	return ret;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		sum += arr[i];
	}
	memset(dp, -1, sizeof(dp));
	cout << solved(0, 0, 0) << endl;

	return 0;
}