반응형

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

 

15243번: Tiling

Domino tiles (or dominoes) are rectangular pieces of size 2x1. Each square contains a number from 1 to 6. These pieces are used to play a game but in this problem we are going to use them for something different. We can build rectangles of certain width W

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 타일을 배치할 총너비가 홀수라면 배치할 방법이 없으므로 0을 출력해 줍니다.

 

2. 너비가 짝수라면 다음과 같은 점화식을 사용하여 문제를 풀어줍니다.

arr[ i ] = arr[ i - 2 ] * 4 - arr[ i - 4 ]

 

3. 수가 int 범위를 넘어갈 수 있으므로 long long 자료형을 쓰고, 1000000007을 Modulo를 통해 답을 출력합니다.

 

[ 소스코드 ]

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
32
#include<iostream>
#define ll long long
#define M 1000000007
using namespace std;
 
ll arr[1001];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int W;
    cin >> W;
 
    arr[0] = 1;
    arr[2] = 3;
 
    if (W % 2 == 0) {
        for (int i = 4; i <= W; i += 2) {
            arr[i] = ((arr[i - 2] % M) * 4) % M - arr[i - 4] % M + M;
            arr[i] %= M;
        }
    }
    else {
        cout << 0;
        return 0;
    }
 
    cout << arr[W];
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 23326번 - 홍익 투어리스트 (C++)  (0) 2023.07.20
[ 백준 ] 21939번 - 문제 추천 시스템 Version 1 (C++)  (0) 2023.07.19
[ 백준 ] 4811번 - 알약 (C++)  (0) 2023.07.17
[ 백준 ] 22856번 - 트리 순회 (C++)  (0) 2023.07.16
[ 백준 ] 7453번 - 합이 0인 네 정수 (C++)  (0) 2023.07.15

+ Recent posts

티스토리툴바