«   2022/08   »
  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 29 30 31      
Archives
Today
11
Total
93,048
관리 메뉴

차근차근

[백준 2133] 타일 채우기 본문

대학교/Algorithm

[백준 2133] 타일 채우기

SWKo 2020. 2. 17. 20:34

0. 제목

  • 백준 2133 타일 채우기
  • BOJ 2133 타일 채우기
  • C++ 2133 타일 채우기

1. 문제

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


2. 풀이

  • 3xN 크기의 벽을 2x1, 1x2 크기의 타일로 채우는 경우의 수를 구하는 것이다.
  • 앞서 풀었던 타일 채우기 문제와는 살짝 달랐다.
  • 앞에서 풀었던 타일 문제들은 N의 값이 늘어날 때 새로운 종류의 타일 모양이 나오지 않았다.
  • 그러나 이 문제는 N이 2씩 늘어날때마다 새로운 모양 2개가 추가적으로 생겼다.
  • 먼저 끝 2칸을 제외하면 3가지 방법이 나온다. 그리고 4칸, 6칸, 8칸.... 제외하면 2가지씩 추가적으로 생긴다.
  • 그리고 3xN의 크기의 벽을 2x1, 1x2로 채우기 위해서는 N이 짝수이어야 한다. N이 홀수이면 넓이가 짝수인 타일들로는 채울 수 없기 때문이다.
  • 그래서 N이 홀수인 경우 dp[N] = 0 이다.
  • 따라서 N에 대하여 점화식을 써보면 다음과 같다.
  • dp[N] = 3*dp[N-2] + 2*dp[N-4] + 2*dp[N-6] + 2*dp[N-8] + ... + 2*dp[0]

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int N;
    int dp[31];
    cin >> N;
    dp[0= 1;
    dp[2= 3;
    if(N % 2 == 1)
        dp[N] = 0;
    else{
        for(int i = 4; i <= N; i += 2){
            dp[i] = 3 * dp[i-2];
            for(int j = 4; j <= i; j += 2){
                dp[i] += 2 * dp[i - j];
            }
        }
    }
    cout << dp[N] << '\n';
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 1476] 날짜 계산  (0) 2020.02.19
[백준 15953] 상금 헌터  (0) 2020.02.17
[백준 2133] 타일 채우기  (0) 2020.02.17
[백준 4963] 섬의 개수  (0) 2020.02.16
[백준 1966] 프린터 큐  (0) 2020.02.16
[백준 2170] 선 긋기  (0) 2020.02.15
0 Comments
댓글쓰기 폼