[백준] 12996-Acka(C++)

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

12996번: Acka

dp 문제입니다.

아이디어 도출이 어려운 문제지만 구현난이도는 최하입니다.

 

 

3명의 친구들이 불러야 하는 곡수와 전체곡의 갯수가 주어지기 때문에 

long long dp[51][51][51][51]; // s,dotorya, kesakiyo, hongjun7 라는 dp배열을 만들어 메모이제이션 하면 됩니다.

 

dp[s][d][k][h]는 s곡 남았을때, 1번 친구가 d개 남고, 2번 친구가 k개 남고, 3번 친구가 h개 남았을때의 최대값을 저장합니다.

 

아래는 정답코드입니다. 막상 구현하니 너무 간단하네요.

주의할 점은 long long을 사용해야 한다는것입니다. 

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

long long dp[51][51][51][51]; // s,dotorya, kesakiyo, hongjun7

long long solved(int s, int d, int k, int h) {

	if (s == 0) {
		if (d == 0 && k == 0 && h == 0)
			return 1;
		else
			return 0;
	}
	
	long long& ret = dp[s][d][k][h];
	if (ret != -1)
		return ret;
	ret = 0;

	ret += solved(s - 1, d - 1, k, h);
	ret += solved(s - 1, d, k - 1, h);
	ret += solved(s - 1, d, k, h - 1);

	ret += solved(s - 1, d - 1, k - 1, h);
	ret += solved(s - 1, d - 1, k, h - 1);
	ret += solved(s - 1, d, k - 1, h - 1);

	ret += solved(s - 1, d - 1, k - 1, h - 1);

	ret %= 1000000007;
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int s, d, k, h;
	cin >> s >> d >> k >> h;

	memset(dp, -1, sizeof(dp));
	cout << solved(s, d, k, h) << endl;

	return 0;
}