Taene's

[백준] Class3-2xn 타일링 2 C++ 11727번 본문

백준/Class3

[백준] Class3-2xn 타일링 2 C++ 11727번

taene_ 2023. 10. 10. 09:55

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

 

11727번: 2×n 타일링 2

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.

www.acmicpc.net

#include<iostream>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	int k[1001] = { 0,1,3,5,11,21, };
	for (int i = 2; i <= n; i++)
	{
		if (i % 2 == 0)
		{
			k[i] = (k[i - 1] * 2 + 1) % 10007;
		}
		else
		{
			k[i] = (k[i - 1] * 2 - 1) % 10007;
		}
	}
	cout << k[n];

	return 0;
}

접근방법: n의 값을 1부터 8정도 까지 값을 구해보고 규칙을 찾아서 점화식을 세운 다음 10007을 나눠준다. (dp문제)

저작자표시

'백준 > Class3' 카테고리의 다른 글

[백준] Class3-유기농 배추 C++ 1012번  (0) 2023.10.16
[백준] Class3-Four Squares C++ 17626번  (1) 2023.10.10
[백준] Class3-2xn 타일링 C++ 11726번  (0) 2023.10.10
[백준] Class3-구간 합 구하기4 C++ 11659번  (0) 2023.10.10
[백준] Class3-파도반 수열 C++ 9461번  (0) 2023.10.09
'백준/Class3' Related Articles more