[Java] baekjoon_11726 : 2×n 타일링

다이나믹 프로그래밍

2×n 타일링 : Silver3

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

풀이

import java.io.*;

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

  public static void main(String[] args) throws IOException {
    int n = Integer.parseInt(br.readLine());

    int[] dp = new int[n + 1];
    dp[1] = 1;
    if (n >= 2)
      dp[2] = 2;
    for (int i = 3; i <= n; i++) {
      dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
    }

    bw.write(dp[n] + "\n");
    br.close();
    bw.close();
  }
}

 

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 점화식은 아래와 같이 정의했다.

먼저, n이 1일 때와 2일 때의 경우를 살펴보면,
n = 1은 1가지 방법 (1×2 타일 하나 사용)
n = 2는 2가지 방법 (1×2 타일 두 개 사용 or 2×1 타일 두 개 사용)
이후, n = 3부터는 이전 단계의 결과를 이용하여, 아래와 같이 점화식을 세울 수 있다.

dp[i] = dp[i - 1] + dp[i - 2] (단, dp[1] = 1, dp[2] = 2)

 

=> 즉, n에 대해 이전 단계의 결과를 활용하여 현재 단계의 값을 구할 수 있다.