[기출] 디자이너의 고민

[조건]

- 시간 제한:  40문항, 1.5초

- Stack: 1MB

 

[문제]

디자이너 조이는 가로 폭이 N인 화면의 배경 디자인을 의뢰 받았다. 

서로 다른 가로 폭을 가진 K 종류의 배경 디자인 조각을 사용하여 디자인을 할 수 있는 방법이 몇 가지인지 찾아보아라.

(답이 굉장히 클 수 있기 때문에 답을 1,000,000,007 로 나눈 나머지를 출력한다.

- 화면 가로 폭: 1 ≤ N ≤ 50,000

- 조각 종류: 2 ≤ K ≤ 100

- 조각의 가로 폭: 1 ≤ A ≤ 1,000

- 각 디자인 조각의 가로 폭은 모두 다르다.

- 각 디자인 조각은 여러 번 사용할 수 있다.

 

[접근법]

1단계: 

경우의 수. 즉 조합 문제로 접근하였다.

경우의 수를 백트래킹으로 구하고, 중복된 숫자를 카운팅하여 nCk 수식으로 구하려고 했다.

그런데 1590!/1582!*8! 이런 계산을 어떻게 할 것인가..

long long 자료형으로 표현 가능한 팩토리얼은 65! 였던 것을 진정 몰랐다.

MOD 를 하면 분모가 커지는 경우 0으로 계산값이 도출되었다.

 

2단계:

n=1 부터 계산하여 현재 값을 직전 계산값을 이용하여 구하는 동적계획법을 이용해야 했다.

우선 DP 점화식에 한번 놀랐고, 집합 개념으로 inc1 & inc2 를 모두 포함하는 경우를

찾아내는 것도 놀라웠다.

현재 조각 k 를 이용하여 만들수 있는 경우의 수는 DP[n-tiles[k]] 로 구하였다.

즉 m(=tiles[k], 상수값) 에 나머지 길이에 대한 경우의 수를 덧붙이는 개념이다.

 

예) N=3, K=3 (1,2,3) 일 때,

n=1 (경우의 수: 1)

n=2 (경우의 수: 11, 2)

n=3 (경우의 수: 111, 12, 21, 3)

 

점화식: DP[n] += DP[n-m]    (m = tiles[k])

예: DP[3] = (m=1) + DP[2]   (경우의 수: 111, 12)

             + (m=2) + DP[1]  (경우의 수: 21)

             + (m=3) + DP[0]  (경우의 수: 3)

 

[알고리즘]

DP

▷유사문제: 

 

[Key Point]

-

 

[구현코드]

// 디자이너의고민.cpp : Defines the entry point for the console application.
//
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>

#define MAX_N 50001
#define MOD 1000000007

int T, N, K;
int inc1, inc2;
int tiles[MAX_N];
int DP[MAX_N], DP1[MAX_N], DP2[MAX_N], DP3[MAX_N];

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		memset(DP, 0, sizeof(DP));
		memset(DP1, 0, sizeof(DP1));
		memset(DP2, 0, sizeof(DP2));
		memset(DP3, 0, sizeof(DP3));

		scanf("%d%d", &N, &K);
		for (int i = 1; i <= K; ++i) {
			scanf("%d", &tiles[i]);
		}

		scanf("%d%d", &inc1, &inc2);

		DP3[0] = DP2[0] = DP1[0] = DP[0] = 1;
		for (int n = 1; n <= N; n++) {
			for (int k = 1; k <= K; k++) {
				int m = tiles[k];
				// 해당 조각을 붙여도 n 이 넘지 않을 때만
				if (n >= m) {
					// n 이 되는 전체 경우의 수 구하기
					// (n - 현재 타일의 길이) 에서 현재 타일을 붙이면 n 이 됨
					DP[n] += DP[n - m];
					DP[n] %= MOD;
					// 1을 안 붙인거
					if (inc1 != k) {
						DP1[n] += DP1[n - m];
						DP1[n] %= MOD;
					}
					// 2를 안 붙인거
					if (inc2 != k) {
						DP2[n] += DP2[n - m];
						DP2[n] %= MOD;
					}
					// 둘다 안 붙인거
					if (inc1 != k && inc2 != k) {
						DP3[n] += DP3[n - m];
						DP3[n] %= MOD;
					}
				}
			}
		}

		// 전체 경우의 수에서 1, 2 안 붙인거를 빼주고
		// 이 때 1, 2 둘다 안 붙인게 한 번 씩, 총 두 번 빠지니까
		// 둘다 안 붙인거 한 번 더해주면 답
		long long result = (DP[N] - DP1[N] - DP2[N] + DP3[N]) % MOD;
		printf("#%d %lld\n", tc, (result < 0) ? result + MOD : result);
	}
	return 0;
}