개요

[링크]백준 11727번: 2xN 타일링 2

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

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

접근 방식

[백준 11726] 과 유사한 방식이다.
F(n)을 2xn에 넣을수 있는 경우의수라고 했을때,

• 마지막에 2x2하나 넣었을때 F(n-2),
• 마지막에 2x1두개 넣었을때 F(n-2),
• 마지막에 1x2 하나 넣었을 때 F(n-1)
  로 나눌 수 있으므로

총 점화식은 F(N)=2*F(N-2)+F(N-1)이라고 할 수 있다.

코드

#include<iostream>

using namespace std;
int dp[1001];
const int devideBy = 10007;

void input(int& amount) {
	cin >> amount;
	dp[1] = 1;
	dp[2] = 3;

}
//F(n)을 2xn에 넣을수 있는 경우의수라고 했을때, 2x2하나 넣었을때 F(n-2), 2x1두개 넣었을때 F(n-2), 1x2하나 넣었을 때 F(n-1)
void solution(int& amount) {
	for (int i = 3; i <= amount; i++) {
		dp[i] = (dp[i - 1]%devideBy + 2*dp[i - 2]%devideBy)%devideBy;
	}
	cout << dp[amount];
}

int main() {
	int amount=0;
	input(amount);
	solution(amount);
}

문풀후생

11726과 비슷한 문제라 어려울 건 없었다.