백준 타일채우기 문제 dp

어려운 문제였다. 많이 헤맸고 내가 헤맸던 과정들을 정리해봐야겠다.

재귀 문제와 점화식 세우는 문제는 정말 유사한 면이 많다.

내가 스스로 짜는거는 도저히 못하겠는데 남들 코드를 보면 정말 신비롭다는 생각이다. 이걸 성공을 하긴 했지만 온전히 내 힘으로 한게 아니기 때문에 언젠가 다시 해결해봐야겠다. 느낀점은 이만하고 이제 문제를 설명해보자.

​

문제는 매우 간단하다. 우리는 일단 문제 이해는 어렵지 않을테니 문제 이해는 넘어가겠다.

​

문제 해결을 위해 길이가 작은 부분부터 문제를 봤다.

우선 첫번째로 이 문제는 길이가 짝수일때만 가능하다. 타일들의 넓이는 다 짝수기 때문에 짝수들을 이용해서 넓이가 홀수인 사각형을 만들 수 없기 때문에 우리는 하나 특징을 찾았다.

1번 특징 : 길이는 반드시 짝수이고 홀수인 경우 0을 출력한다.

다음은 이 문제 해결을 위해 작은 숫자부터 대입을 해보았다. 일단 길이가 2인경우

우리는 3가지 경우가 있는걸 알수가 있다.

테블릿으로 풀면서 그려서 ㅎㅎ

이렇게 3가지 경우가 있다는걸 알수가 있다.

​

이제 길이가 4인 경우를 살펴보자.

4인 경우는 이렇게 길이가 2인 경우로 2개가 나뉘어서 3*3 가지 방법과 4인경우 생기는 특이한 방법이 2가지가 생긴다.

그래서 4인 경우는 3*3+2 즉 11가지 방법이 있다.

아직 우리는 두개 밖에 안 해봤으니까 규칙을 찾긴 어렵다 자 바로 길이 6으로 넘어가보자.

​

이렇게 된다 즉 길이가 4인 경우 가지수는 11개 였고 길이가 2인 경우 가지수가 3개 였으니까 그리고 저기서 길이가 6일때만 존재하는 특이한 놈이 또 생긴다. 이를 수식으로 표현하면

11*3 +2 라고 된다...... 라고 생각했다면 당신은 하수이다.

왜냐 이 부분에서는 우리는 어떤 예외에 대해서 생각을 해야한다. 바로 4의 특이 케이스가 오른쪽에 있는 경우이다.

그렇기에 우리는 여기서 3*2를 더해줘야한다 즉 수식은 11*3+3*2+2 가 된다.

우리는 이 과정들을 반복하면서 어떤 규칙성을 발견 할 수 있다. 바로

2. 숫자가 2가 증가할때마다 그 길이에서만 생기는 특별한 경우가 2가지가 발생한다.

내 머리와 구글님들

자 이걸 발견한 후에 우리가 하나 아래에서 헷갈렸던 것 처럼 특이 케이스들이 왼쪽에만 있는 경우 말고 오른쪽에 있는 경우도 생각을 해줘야만한다.

우리는 여기서 규칙성을 발견해서 점화식을 세울 수있다. 하지만 바로 식을 세우면 헷갈릴 사람들이 있으니까 그림으로 더 설명을 해보겠다.

​

여기서 특이라는건 2개이다. 즉 방법은 식으로 세우자면 n의 경우 방법의 수 = (n-2 의 경우) * 3 + (n-4경우)*2+ (n-6경우)*2+ (n-8경우)*2....+2 가 된다.

이걸 점화식으로 수학적으로 표현하면

dp[n]=dp[n-2]*3+sum(dp[2~n-4])+2가 된다.

여기서 3은 dp[2] 가 되고 2는 계속 각 길이별 특의 케이스이다.

각 길이별 특이케이스가 왼쪽에 들어오는 경우들을 다 더해주는 방식으로 한다.

dp[n]=dp[n-2]*3+sum(dp[2~n-4])+2

 

이 점화식을 사용해서 c를 활용한 코드는

 

#include<stdio.h>

int main()
{
	int input;
	int dp[31] = { 0 };
	scanf("%d", &input);
	dp[0] = 0;
	dp[2] = 3;
	dp[4] = 11;
	
	for (int i = 3; 2 * i <= input; i++)
	{
		int sum = 0;
		for (int j = 1; j <= i-2; j++)
		{
			sum += dp[2*j];
		}
		dp[2 * i] = 3 * dp[2 * i - 2] + 2*sum+2;
	}
	printf("%d", dp[input]);
}

이와같다.

오래 걸린 문제지만 완벽하게 풀지 못한 것 같아서 살짝 찝찝한 느낌은 있지만 그래도 나름 뿌듯하다.

이게 골드 5면 도대체 플레랑 골드 상위권 문제들은 얼마나 어려운거냐...

 

이 글은 코딩 꼬꼬마 시절에 푼 문제를 보관한 글로 네이버에 저장해둔 글을 옮긴 글입니다.
혹시나 참고하시는 부분에 이상한 부분이나 질문이 생긴다면 남겨주시면 친절히 답변 드리겠습니다.