11726번: 2×n 타일링

문제링크

CPP

#include <iostream>

using namespace std;

int memo[1001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    memo[1] = 1;
    memo[2] = 2;
    for (int i = 3; i <= n; i++)
        memo[i] = (memo[i - 1] + memo[i - 2]) % 10007;
    cout << memo[n] << "\n";
}

Python

import sys
input = sys.stdin.readline

arr = [0]
arr.append(1)
arr.append(2)
N = int(input())
for i in range (3, N + 1):
    temp = (arr[i - 1] + arr[i - 2]) % 10007
    arr.append(temp)
print(arr[N])

$i \geq 3$부터 점화식을 찾을 수 있다.
$i \times 2$칸을 채울 수 있는 경우의 수는 다음 두 가지로 나눠서 볼 수 있다.

• $(i - 1) \times 1$칸을 채우고 마지막 한 칸을 세로로 집어넣는 경우의 수
• $(i - 2) \times 2$칸을 채우고 마지막 $2 \times 2$칸을 가로로 눕혀서 채우는 경우의 수(세로로 채우는 경우의 수는 바로 이전 케이스에 이미 포함되어 있다)

따라서 $memo[i] = memo[i - 1] + memo[i - 2]$의 점화식을 구할 수 있고 이를 통해 코드를 구성했다.

 

처음에 10007로 나눈 나머지를 출력하라는 것을 생각안하고 제출해서 틀렸다.

매번 덤벙대지 않도록 조심해야겠다.