문제 설명
빨강, 파랑, 초록색의 장난감으로 크리스마스 트리 위에서부터 꾸몄을 때 경우의 수를 출력하면 되는 문제입니다.
풀이
문제를 처음 보고 DP 문제구나 싶어서 dp[n][r][g][b]에 값을 저장하려고 했습니다.
dp[레벨][남은 빨간색 장난감][남은 초록색 장난감][남은 파란색 장난감] = 레벨 1 ~ 현재 레벨까지 남은 장난감에 따른 경우의 수
dp[11][101][101][101]이다 보니 메모리를 줄일 수 있는 방법이 없을까 생각해보다가 레벨 1부터 10까지 한 가지 색만 선택해도 55개를 사용하기 때문에 100개까지 필요 없고 56개 이상 장난감을 갖고 있을 때 55개를 갖고 있다고 해도 됩니다.
그러므로 dp[11][56][56][56]으로 메모리를 줄일 수 있고 여기서 남은 장난감 중에 한 가지를 따로 배열 인덱스로 쓰지 않아도 됩니다.
남은 파란색 장난감 = 총 파란색 장난감 - (레벨 - (총 빨간색 장난감 - 남은 빨간색 장난감) - (총 초록색 장난감 - 남은 초록색 장난감))
으로 남은 파란색 장난감을 나머지 3개 값으로 알 수 있습니다.
그러므로 남은 파란색 장난감은 배열 인덱스에서 제외하겠습니다.
그러면 dp[레벨][남은 빨간색 장난감][남은 초록색 장난감] - dp[11][56][56]으로 메모리를 줄일 수 있습니다.
이제 dp 배열에 저장하는 방식을 설명하겠습니다.
먼저 한 레벨 n에 빨강, 파랑, 초록색 장난감의 개수를 동일하게 하여 n 개의 장난감을 장식해야 합니다.
3가지 색상을 분해하는 방법은 7가지 방법이 있습니다.
한 가지 색을 레벨 n에 장식하는 방법 3가지, 두 가지 색을 레벨 n에 장식하는 방법 3가지,
세 가지 색을 레벨 n에 장식하는 방법 1가지
한 가지 색으로만 장식하는 방법은 어느 레벨에서든 다 됩니다.
두 가지 색으로 장식하는 방법은 레벨이 2의 배수일 때 가능합니다.
세 가지 색으로 장식하는 방법은 레벨이 3의 배수일 때 가능합니다.
물론 장식하려고 하는 장난감의 개수가 남아있는 장난감의 개수보다 작거나 같아야 합니다.
그리고 레벨에 장난감들을 배치하는 순서(빨강 1개, 초록 1개를 장식한다 하면 빨강, 초록 혹은 초록, 빨강)에도
경우의 수를 다르게 세어줘야 하기 때문에 구해줍니다.
장식하려는 모든 경우의 수에서 같은 색에 해당하는 중복만 제외해주면 됩니다.
레벨에 장식하려는 모든 경우의 수 / (빨간색끼리 장식하는 경우의 수 * 초록색끼리 장식하는 경우의 수 * 파란색끼리 장식하는 경우의 수)
중, 고등학교쯤에 배웠던 중복을 제외한 경우의 수를 구하는 식을 사용하면 됩니다.
그렇게 dp 배열 값을 저장해주면 AC를 받을 수 있습니다.
시간 복잡도는 O(n * r * g)입니다.
소스 코드
#include <cstdio>
#include <cstring>
#define min(a,b) (a < b ? a : b)
typedef long long ll;
ll dp[15][60][60];
int f[15];
int n, red, green, blue;
int d[7][3] = { {1,0,0},{0,1,0}, {0,0,1},{1,1,0},{1,0,1},{0,1,1},{1,1,1} };
void get_factorial(int n) {
f[0] = 1;
for (int i = 1; i <= n; i++)
f[i] = f[i - 1] * i;
}
ll get_dp(int lv, int r, int g, int b) {
if (lv == n + 1) return 1;
ll& ret = dp[lv][r][g];
if (ret != -1) return ret;
ret = 0;
for (int i = 0; i < 7; i++) {
if (lv % (i / 3 + 1)) continue;
int val = lv / (i / 3 + 1);
int nr = r - d[i][0] * val, ng = g - d[i][1] * val, nb = b - d[i][2] * val;
if (nr < 0 || ng < 0 || nb < 0) continue;
ll cnt = 1LL * f[lv] / (f[d[i][0] * val] * f[d[i][1] * val] * f[d[i][2] * val]);
ret += cnt * get_dp(lv + 1, nr, ng, nb);
}
return ret;
}
int main() {
memset(dp, -1, sizeof(dp));
scanf("%d %d %d %d", &n, &red, &green, &blue);
get_factorial(n);
red = min(red, 55);
green = min(green, 55);
blue = min(blue, 55);
printf("%lld\n", get_dp(1, red, green, blue));
return 0;
}