본문으로 바로가기

2xn개의 타일링을 채우기 위해서 3가지 상황을 가정하자. 세로로 타일 하나를 놓은 경우 나머지 2*(n-1)개의 타일링을 채우는 방법과 가로로 2개를 놓아 나머지 2*(n-2)개의 타일링을 채우는 방법 그리고 2x2 타일 하나를 놓아 나머지 2*(n-2)개의 타일링을 채우는 방법, 3가지를 더하면 된다. 또한 중복 계산을 피하기 위해 다이나믹 프로그래밍으로 한 번 계산한 값을 배열에 저장해놓는다.

#include <cstdio>

int dp[1001];
int f(int);

int main() {
  int n;
  scanf("%d", &n);
  printf("%d\n", f(n));
  return 0;
}

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 3;
  if (dp[n]) return dp[n];

  // 임의의 n개에 대하여
  // 세로로 하나 놓았을 경우 나머지 (n-1)개를 채우는 방법 +
  // 가로로 2개 놓았을 경우 나머지 (n-2)개를 채우는 방법 +
  // 2x2 타일을 하나 놓았을 경우 나머지  (n-2)개를 채우는 방법
  return dp[n] = (f(n-1) + 2*f(n-2)) % 10007;
}

'Programming > Baekjoon Online Judge' 카테고리의 다른 글

[BOJ] 11052: 붕어빵 판매하기  (0) 2018.05.15
[BOJ] 9095: 1, 2, 3 더하기  (0) 2018.05.15
[BOJ] 11727: 2xn 타일링 2  (0) 2018.05.15
[BOJ] 11726: 2xn 타일링  (0) 2018.05.15
[BOJ] 1463: 1로 만들기  (0) 2018.05.15
[BOJ] 11656: 접미사 배열  (0) 2018.05.14

댓글을 달아 주세요