2×n 타일링

문제

2×n 타일링

풀이

가로 타일을 이용해 채우는 경우 무조건 가로 타일 2개를 사용하여 2x2 형태로 채워야 합니다. 따라서 세로 타일과 2x2 타일만 있다고 생각하고 풀어도 됩니다.

번째 열 까지 타일을 채우는 방법의 수를 라 합시다. 열까지 채우는 경우는 열까지 채운 경우에서 세로 타일을 채우거나 열까지 채운 경우에서 가로 타일 두개를 채우는 경우입니다. 따라서 아래 점화식을 통해 답을 구할 수 있습니다.

코드

아예 채우지 않는 방법의 수는 입니다. 로 두고 를 채우면 됩니다.

Python

MOD = 10_007
 
n = int(input())
 
dp = [0] * (n + 1)
 
dp[0] = 1
dp[1] = 1
 
for i in range(2, n + 1):
    dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
 
print(dp[n])

C++

#include <bits/stdc++.h>
using namespace std;
 
constexpr int MOD = 10'007;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
    vector<int> dp(n + 1);
 
    dp[0] = 1;
    dp[1] = 1;
 
    for (int i = 2; i <= n; i++)
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
 
    cout << dp[n];
 
    return 0;
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
    static final int MOD = 10_007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
        int dp[] = new int[n + 1];
 
        dp[0] = 1;
        dp[1] = 1;
 
        for (int i = 2; i <= n; i++)
            dp[i] = (dp[i-1] + dp[i-2]) % MOD;
 
        bw.write(dp[n] + "");
 
        bw.close();
    }
}