[C++]백준 - 11726번 문제

11726번: 2×n 타일링 (acmicpc.net)

11726번: 2×n 타일링

 

11726번 : 2 X n 타일링

---

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

 

입력

---

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

 

출력

---

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

 

 

---

 

생각해 볼 점

---

DP 문제입니다.

 

가로 좌표에 따라 DP배열을 구성하고,

 

경우의 수를 담아서 해결하면 될 것입니다.

 

0번째 칸부터 끝까지 채우는 방법의 수 = DP[0]

 

0번째 칸을 채울 방법은 2가지

 

1. 수직으로 한칸을 채우고, 나머지 경우의 수를 생각한다.

2. 수평으로 두칸을 채우고, 나머지 경우의 수를 생각한다.

 

따라서,

DP[0] = DP[1] + DP[2] 가 성립하고, 이를 DP[N-1]까지 반복하면 됩니다.

 

 

코드

---

#include <iostream>
using namespace std;

int solution(int *& dp, int const &now, int const& N)
{
	if (N < now) return 0;
	if (now == N) return 1;
	if (dp[now] != 0) return dp[now];

	return dp[now] = (solution(dp, now + 1, N) + solution(dp, now + 2, N)) % 10007;
}

int main()
{
	int N;
	scanf("%d", &N);
	int* dp = new int [N + 1];
	fill_n(dp, N, 0);

	printf("%d", solution(dp, 0, N));

	delete[] dp;
	return 0;
}

 

그 외

---