[Java] baekjoon_11727 : 2×n 타일링 2

다이나믹 프로그래밍

2×n 타일링 2 : Silver3

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

11727번: 2×n 타일링 2

 

ㄴ 주어진 문제는 2×n 직사각형을 1×2, 2×1, 그리고 2×2 타일로 채우는 방법의 수를 구하는 문제이다.

ㄴ  2×n 타일링 문제의 심화 문제이다..!

ㄴ 이를 해결하기 위해 다이나믹 프로그래밍(DP : Dynamic Programming)을 이용했다.

 

 

첫 번째 작성한 코드

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] = 3;
    }
    
    for (int i = 3; i <= n; i++) {
      dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
    }

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

 

ㄴ 여기서는 주어진 직사각형을 가로로 나눌 때 마지막에 사용하는 타일의 종류에 따라 경우의 수를 나눠서 생각할 수 있다.

ㄴ  마지막에 사용하는 타일의 종류에는 1×2 타일, 2×1 타일, 그리고 2×2 타일이 있다.

 

만약 마지막에 1×2 타일을 사용한다면, 이전까지의 상황은 2×(n-1) 직사각형을 채우는 방법의 수와 같다.
만약 마지막에 2×1 타일을 사용한다면, 이전까지의 상황은 2×(n-2) 직사각형을 채우는 방법의 수와 같다.
만약 마지막에 2×2 타일을 사용한다면, 이전까지의 상황은 2×(n-2) 직사각형을 채우는 방법의 수와 같다.

 

따라서 점화식은 다음과 같이 세울 수 있다.

dp[n] = dp[n-1] + dp[n-2]*2

여기서 dp[i]는 2×i 크기의 직사각형을 채우는 방법의 수를 나타낸다.

마지막에 사용하는 타일의 종류에 따라서 경우의 수가 달라지므로, 위와 같은 점화식을 사용하여 문제를 해결했다.

또한, 문제에서는 결과를 10007로 나눈 나머지를 출력하라고 명시하고 있으므로, 결과값을 10007로 나눈 나머지를 출력해야 한다.

 

dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;

 

결과적으로 위와 같은 식이 도출된다.

 

 

두 번째 작성한 코드

import java.io.*;

public class Main {
  private static final int MOD = 10007;

  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] = 3;
    }
    
    for (int i = 3; i <= n; i++) {
      dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % MOD;
    }

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

 

ㄴ 첫 번째 작성한 코드에서 10007을 바로 써줬었는데, 두 번째 작성한 코드에서는 private static final int MOD = 10007; 처럼 final을 이용해서 정의해주었다.