[주의][다이나믹 프로그래밍] 타일 채우기

문제 링크 : https://www.acmicpc.net/problem/2133

타일 채우기 성공 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 11565 4028 3142 35.319% 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1  2 예제 출력 1  3 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다.

[ 문제 풀이 ]

D[i]를 3 x i 벽을 타일로 채울 수 있는 경우의 수로 둔다.

경우의 수를 계산해보면,

즉, D[i] = D[i-2] x 3 + D[i- 4] x 2

D[i - 6] x 2

D[i - 8] x 2

...

D[0] x 2

※ 주의. 경우의 수에서 D[0] = 1 (아무것도 없는 방법 1가지) 로 두어야 하는지 생각해볼 것.

※ 주의. 이 문제에서는 경우의 수가 이전에서 연속되는 경우 곱하기임에 유의할 것.

[ 최종 구현(C++) ]

#include <stdio.h>
#define MAX_NUMBER 100002
int D[MAX_NUMBER] = { 0, };

int main(void)
{
	int N;
	scanf("%d", &N);

	D[1] = 1;
	
	for (register int i = 2; i <= N; i++)
	{
		D[i] = i;

		for (register int j = 1; j*j <= i; j++)
		{
			D[i] = D[i] < D[i - j*j] + 1 ? D[i] : D[i - j*j] + 1;
		}
	}

	printf("%d\n", D[N]);


	return 0;
}