백준(BOJ) 12996번 Acka

문제 : https://www.acmicpc.net/problem/12996

12996번: Acka

 

풀이 :

 

한 앨범당 가질수 있는 경우의 수는 7가지 이다

 

( a만 b만 c만 a,b만 a,c만 b,c만 a,b,c )

 

따라서 각각의 경우의 수를 모두 재귀호출 해준 후 중복은 메모이제이션으로 없애자.

 

코드 ( C++ )

	#include <iostream>
	#include <cstring>
	using namespace std;
	const int mod = 1000000007;
	long long cache[51][51][51][51];
	long long solve(int S, int a, int b, int c)
	{
	if (S == 0) {
	if (a == 0 && b == 0 && c == 0) {
	return 1;
	}
	else return 0;
	}
	if (a < 0 || b < 0 || c < 0) return 0;
	long long& ret = cache[S][a][b][c];
	if (ret != -1)
	return ret;
	ret = 0;
	ret += solve(S - 1, a - 1, b, c);
	ret += solve(S - 1, a , b-1, c);
	ret += solve(S - 1, a, b, c-1);
	ret += solve(S - 1, a - 1, b-1, c);
	ret += solve(S - 1, a - 1, b, c-1);
	ret += solve(S - 1, a, b-1, c-1);
	ret += solve(S - 1, a - 1, b-1, c-1);
	ret %= mod;
	return ret;
	}
	int main()
	{
	int S, a, b, c;
	cin >> S >> a >> b >> c;
	memset(cache, -1, sizeof(cache));
	cout << solve(S, a, b, c);
	}

view raw .cpp hosted with ❤ by GitHub