문제

BOJ 11727, 2×n 타일링 2

핵심

• 입력의 크기가 $10^3$이라 구현에 초점을 맞춘다.
• 2xn 직사각형을 1x2, 2x1과 2x2 타일로 채우는 방법의 수를 구해야 한다. 2xn 타일링 문제를 풀어봤다면 dp문제임을 쉽게 알아차릴 수 있지만 처음 보면 이것을 dp로 접근하기가 어려울 수 있다.
• dp[i]: 가로의 너비가 i일 때 채울 수 있는 타일의 개수.
• dp[1] = 1;
  • |
• dp[2] = 3;
  • ㅁ
  • | |
  • ㅡ
• dp[3] = 5;
  • | ㅁ
  • ㅁ |
  • | | |
  • ㅡ |
  • | ㅡ
• dp[4] = 11;
  • | | ㅁ
  • | ㅁ |
  • ㅁ | |
  • ㅁ ㅁ
  • ㅁ ㅡ
  • | | | |
  • ㅡ ㅁ
  • | | ㅡ
  • | ㅡ |
  • ㅡ | |
  • ㅡ ㅡ
• 초기식을 정하다 보면 규칙이 보이는데, dp[i] = dp[i - 2] * 2 + dp[i - 1]로 구할 수 있다. 물론 해당 예시에선 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]으로 점화식을 생각할 수도 있겠지만 주어진 예시와 ㅁ 자리에 ㅡ 이 들어올 수 있다는 것을 생각하면 규칙을 쉽게 찾을 수 있다.

개선

코드

시간복잡도

• $O(N)$

C++

#include <iostream>
using namespace std;

int dp[1004];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	dp[1] = 1;
	dp[2] = 3;
	dp[3] = 5;
	for (int i = 3; i <= 1000; ++i)
		dp[i] = (dp[i - 2] * 2 + dp[i - 1]) % 10'007;
	cout << dp[n];
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[1004];
        dp[1] = 1;
        dp[2] = 3;
        dp[3] = 5;
        for (int i = 3; i <= 1000; ++i)
            dp[i] = (dp[i - 2] * 2 + dp[i - 1]) % 10_007;
        System.out.println(dp[n]);
        sc.close();
    }
}