[伯俊]17261727-C++

11726. 2×nタイル

https://www.acmicpc.net/problem/11726

Brute Force-タイムアウト

#include <stdio.h>
#include <iostream>

#define MAXN 1005

int n;
int answer;
int box[2][MAXN];

void func(int idx, int cnt)
{
	if(idx == n) {
		answer++;
		return;
	}

	int i = idx;

	if(i < n-1) {
		if(box[0][i] == 0) {
			// 세로
			box[0][i] = 1;
			box[1][i] = 1;
			func(idx+1, cnt+1);
			box[0][i] = 0;
			box[1][i] = 0;

			// 가로
			box[0][i] = 1;
			box[0][i+1] = 1;
			func(idx, cnt+1);
			box[0][i] = 0;
			box[0][i+1] = 0;
		}
		else if(box[1][i] == 0) {
			// 가로
			box[1][i] = 1;
			box[1][i+1] = 1;
			func(idx+2, cnt+1);
			box[1][i] = 0;
			box[1][i+1] = 0;
		}
	}
	else {
		if(box[0][i] == 0) {
			// 세로
			box[0][i] = 1;
			box[1][i] = 1;
			func(idx+1, cnt+1);
			box[0][i] = 0;
			box[1][i] = 0;
		}
		else if(box[1][i] == 0) {
			return;
		}
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);

	scanf("%d", &n);

	func(0, 0);

	printf("%d", answer % 10007);

	return 0;
}

直接2 nの長方形を作成し、1.2*1の長方形を直接埋めます.
やはりタイムアウトだ.
DPの使用:
そこでまずルールを調べてみると、n番目の値はn-2番目とn-1番目の和であることがわかりました.
ビボナッチを使いましょう!!

戻る-タイムアウト

#include <stdio.h>
#include <iostream>

#define MAXN 1005

int n;
int answer;
int num[3];

int func(int N)
{
	if(N < 3) {
		return num[N-1] % 10007;
	}
	return (func(N-2) + func(N-1)) % 10007;
}

int main()
{
	//freopen("input.txt", "r", stdin);

	scanf("%d", &n);
	
	num[0] = 1;
	num[1] = 2;
	num[2] = 3;

	answer = func(n);

	printf("%d", answer % 10007);

	return 0;
}

最も基本的な才能を利用したフィボナッチ.
->タイムアウト

DP-成功

#include <stdio.h>
#include <iostream>

#define MAXN 1005

int n;
int answer;
int num[MAXN];

int func(int N)
{
	if(N < 3) {
		num[N] = num[N] % 10007;
	}
    else if(num[N-2] && num[N-1]) {
		num[N] = (num[N-2] + num[N-1]) % 10007;
	}
	else if(num[N-2]) {
		num[N] = (num[N-2] + func(N-1)) % 10007;
	}
	else if(num[N-1]) {
		num[N] = (func(N-2) + num[N-1]) % 10007;
	}
	else {
		num[N] = (func(N-2) + func(N-1)) % 10007;
	}
	return num[N];
}

int main()
{
	//freopen("input.txt", "r", stdin);

	scanf("%d", &n);
	
	num[0] = 0;
	num[1] = 1;
	num[2] = 2;

	answer = func(n);

	printf("%d", answer % 10007);

	return 0;
}

DP値を使用した再帰に変更し、パスしました!
取得した値はDP値を使用します.
まだもらっていないお金を返しました.

DP 2-成功

#include <stdio.h>
#include <iostream>

#define MAXN 1005

using namespace std;

int N;
int nums[MAXN];
int ans;

int main()
{
	//freopen("input.txt", "r", stdin);

	scanf("%d", &N);

	nums[0] = 0;
	nums[1] = 1;
	nums[2] = 2;

	for (int i = 3; i <= N; i++) {
		nums[i] = (nums[i - 1] + nums[i - 2]) % 10007;
	}

	printf("%d", nums[N]);

	return 0;
}

複文を使わず、複文だけでより簡単に解くことができます.
点火式=>nums[n] = nums[n-1] + nums[n-2]
注)https://assb.tistory.com/entry/%EB%B0%B1%EC%A4%80-11726%EB%B2%88-2xn-%ED%83%80%EC%9D%BC%EB%A7%81

11727. 2×nタイル2

https://www.acmicpc.net/problem/11727

DP-成功

#include <stdio.h>
#include <iostream>

#define MAXN 1005

using namespace std;

int N;
int nums[MAXN];
int ans;

int main()
{
	//freopen("input.txt", "r", stdin);

	scanf("%d", &N);

	nums[0] = 0;
	nums[1] = 1;
	nums[2] = 3;

	for (int i = 3; i <= N; i++) {
		nums[i] = (nums[i - 1] + nums[i - 2] * 2) % 10007;
	}

	printf("%d", nums[N]);

	return 0;
}

11726題で応用して適切な点火方式を見つけた.
2×2の矩形を増やしたので、2×2の大きさを埋めることができる矩形は2種類あります.
=>nums[i-2] * 2.