0%

[백준/11727] 2×n 타일링 2

작성일 Edited on In Disqus:

Baekjoon Online Judge - 11727

Review

  • 백준 11726번 문제를 조금만 바꾸면 된다.
  • 2x2 타일이 추가된 것이므로, 그 말인 즉슨 n-2인 경우가 2배가 된다는 것이다.
  • 점화식은 A[n] = A[n-1] + A[n-2] * 2
  • 참고로 memo[2]일 경우의 값을 3으로 바꿔주어야 한다. 직사각형이 2x2 크기인 경우의 경우의 수가 3이기 때문.

Code 1 (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.io.*;

public class Main {

  static long[] memo;

  public static long tile(int n) {
    if(n == 1) {
      memo[1] = 1;
      return memo[1];
    } else if(n == 2) {
      memo[2] = 3;
      return memo[2];
    } else if(memo[n] != 0) {
      return memo[n] %= 10007;
    } else {
      memo[n] = tile(n - 1) + tile(n - 2) * 2;
      return memo[n] %= 10007;
    }
  }

  public static void main(String args[]) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int input = Integer.parseInt(bf.readLine());
    memo = new long[input + 1];
    System.out.println(tile(input));
  }
}

Code 2 (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.io.*;

public class Main {

  public static void main(String args[]) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int input = Integer.parseInt(bf.readLine());
    long[] memo;

    memo = new long[1001];

    memo[1] = 1;
    memo[2] = 3;

    for(int i = 3; i <= input; i++) {
      memo[i] = (memo[i-1] + memo[i-2] * 2) % 10007;
    }

    System.out.println(memo[input]);
  }
}