백준 11726번 : 2xn 타일링 [C언어]

문제출처

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

2xn짜리 타일을 1x2 2x1 타일로 몇가지 채울 수 있는지 구하는 문제다.

규칙을 찾으면 알고리즘 자체는 쉽게 파악할 수 있는데

직접 그림을 그려서 풀면

n=1 일때 1가지

n=2 일때 2가지

n=3 일때 3가지

n=4 일때 5가지

n=5 일때 8가지

...

이 나옴을 알 수 있다.

 

피보나치 수열과 비슷해서 처음에는 재귀를 사용해서 문제를 풀었다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int sq[1001] = { 0 };
int check(int n)
{
	int a, b;
	int ans = 0;

	if (n == 0)
		return 0;
	if (n == 1)
		return 1;
	if (n == 2)
		return 2;
	
	sq[n] = check(n - 1) + check(n - 2);

	return sq[n];
	
}
int main()
{
	int n, ans;

	scanf("%d", &n);

	ans = check(n);

	printf("%d\n", ans % 10007);
}

결과는 시간초과. n이 1000까지 입력되므로 만약 1000이 진행된다면 재귀를 엄청나게 많이 하게 된다.

 

이 문제가 메모이제이션 문제임을 깜빡했다.

sq에 저장된 값을 활용하도록 코드를 수정했다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int sq[1001] = { 0 };
int check(int n)
{
	if (n == 0)
		return 0;
	if (n == 1)
		return 1;
	if (n == 2)
		return 2;
	
	if (sq[n - 2] == 0)
		sq[n - 2] = check(n - 2);
	if (sq[n - 1] == 0)
		sq[n - 1] = check(n - 1);
	
	sq[n] = sq[n - 2] + sq[n - 1];

	return sq[n];
	
}
int main()
{
	int n, ans;

	scanf("%d", &n);

	ans = check(n);

	printf("%d\n", ans % 10007);
}

결과는 틀렸다...

 

질문게시판을 뒤지면서 반례를 입력하다보니

1000을 입력했을 때 정답은 1115가 나와야하는데 내 코드로는 282가 출력된다.

100을 입력했을 때도 음수가 출력되는 문제가!

 

int의 값을 넘는가 해서 자료형을 long long으로 바꿔주어도 계속 오답이 출력되어서 그냥 중간중간에 값을 %10007해주는 식으로 방법을 바꾸었다.

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int sq[1001] = { 0 };
int check(int n)
{
	if (n == 0)
		return 0;
	if (n == 1)
		return 1;
	if (n == 2)
		return 2;
	
	if (sq[n - 2] == 0)
		sq[n - 2] = check(n - 2) % 10007;
	if (sq[n - 1] == 0)
		sq[n - 1] = check(n - 1) % 10007;
	
	sq[n] = (sq[n - 2] + sq[n - 1]) % 10007;

	return sq[n];
	
}
int main()
{
	int n, ans;

	scanf("%d", &n);

	ans = check(n);

	printf("%d\n", ans % 10007);
}

이렇게 바꿔주니 정답이었다.

개인적으로 중간중간 10007로 나누어주면 뭔가 값에 변동이 생기는거 아닌가? 하는 의문점이 생기지만 질문게시판에서도 중간중간에 나누어 주는게 좋다고 하니.... 

나중에 좀 더 찾아봐야할거 같다.