c언어 14852번 타일 채우기 (백준)

#include <stdio.h>

long long int dp[1000001] = {0};
long long int dp2[1000001] = {0};
int n;
void loop(int k)
{
	dp2[k] = dp[k-3] + dp2[k-1];
	dp2[k] %= 1000000007;
	dp[k] += 2*dp[k-1] + 3*dp[k-2] + 2*dp2[k];
	dp[k] %= 1000000007;
	
	if(k >= n) return;
	loop(k+1);
}

int main(void)
{
	scanf("%d", &n);
	dp[0] = 1;
	dp[1] = 2;
	dp[2] = 7;
	loop(3);
	printf("%lld", dp[n]);
	return 0;
}

 

 

14852번: 타일 채우기 3 (acmicpc.net)

14852번: 타일 채우기 3

 

점화식을 구해야 한다.

 

2 * 1 일 때의 경우의 수 : 2 (2*1타일 1개 또는 1*1 타일 2개)

 

■■  or ■■

 

2 * 2 일 때의 경우의 수 (단 2 *1 을 채운 방식을 제외한) : 3

 

■■   ■■   ■■ 

■■   ■■   ■■ 

 

그러므로  일단은 점화식은

 

dp[k] = 2 * dp[k-1] + 3 * dp[k-2] 이다.

 

n==3부터는 1*1타일과 1*2타일 조합이 2개씩 계속 생겨난다.

(n == 3)

■■ ■■

■■ ■■ 

■■ ■■  

 

(n == 4)

■■ ■■

■■ ■■ 

■■ ■■ 

■■ ■■

 

(n == 5)

■■ ■■

■■ ■■ 

■■ ■■ 

■■ ■■ 

■■ ■■

 

이제 다시 점화식을 구해보면

일반적인 경우 : dp[k] = 2 * dp[k-1] + 3 * dp[k-2] 

특이한 경우 : n이 증가 할 때마다 새로운 타일의 경우의 수가 2씩 증가한다!

n==3 일 때는 2개

n==4 일 때는 2개가 또 추가되며, 그전 n==3 있던 것과 관련된 경우의 수는 2*2  (== 2*dp[1]) 4개가 된다.

n==5 일 때는 2개가 또 추가되며, 그전 n==4 있던 것과 관련된 경우의 수는 2*2  (== 2*dp[1]), 또 n==3에 있던 것과 관련된 경우의 수는 2*7 (==2*dp[2]) 가 된다.

n	0	1	2	3	4	5
일반적인 경우	없다 (그래서 1)	2*1	2*2 + 3*1	2*7 + 3*2 = 20	2*22 + 3*7	2*71 + 3*22
특이한 경우				2	2 + 2*2	2 + 2*2 + 2*7
총합	1	2	7	22	71	228

 

특이한 경우를 다시 보면

2 -> 2 + 2*2 -> 2 + 2*2 + 2*7이며 이는

1 -> 1+2 -> 1+2+7 에 2를 전체적으로 곱한 것과 같으며,

또한 이는 dp[0] -> dp[0]+dp[1] -> dp[0] + dp[1] + dp[2] 와 같다.

 

특이한 경우만을 담는 dp2 배열을 만든 후 이에대한 점화식을 구하면,

dp2[k] = dp[k-3] + dp2[k-1] (k>=3) 와 같다.

여기 dp2[]에 2를 곱하면 특이한 경우의 합이 나온다.

 

일반적인 경우와 특이한 경우를 dp[]에 합친다면,

 

dp[k] = 2*dp[k-1] + 3*dp[k-2] + 2*dp2[k] (k>=3) 이라는 점화식이 만들어진다.