백준 11727 2xn 타일링 2

작성일 | In |

Problem : 2xn 타일링2

유형 : DP

문제 설명

2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.

그림

예제 입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

1
2

예제 출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

1
3

해결 전략

끝 지점에 타일을 놓을때, 이전까지 타일을 몇개 놓았는지를 이용해 해결한다.
놓일 수 있는 타일의 종류는 2x1 세로 하나 , 2x1 가로 두개, 2x2 총 3개이다

2x1 직사각형이 있다면, 놓을 수 있는것은 2x1 세로 하나의 경우 하나 밖에 없다.
2x2 의 경우에는, 2x1 세로 하나를 2개 놓은 경우 하나와
2x1 가로 두개를 놓은 경우 하나
2x2 를 놓은 하나
총 3가지의 경우가 존재한다.

2x3의 경우에는 2x2 까지의 경우의 수 + 2x1 까지의 경우의 수 + 2x1 까지의 경우의 수
를 따지면된다. 3 + 1 + 1 = 5

2x4의 경우에는 2x3 까지의 경우의 수 + 2x2 까지의 경우의 수 + 2x2 까지의 경우의 수
를 따지면된다. 5 + 3 + 3 = 11

이것은 끝을 n으로 하는 타일을 배치할때, 앞에 몇개의 타일이 들어갔는지를 찾으면된다.
dp[n] 은 끝을 n으로 하는 타일의 배치 개수 로 잡는다.
dp[n] = dp[n-1] + dp[n-2] + dp[n-2] 라는 점화식을 세울 수 있다.

주의할 점

  • dp문제의 기본은 큰 문제를 작은 문제로 나누어 풀 수 있는가?
    • 중복이 되는가?
    • 중복이 안되는 경우는 분할 정복

  • 중간에 mod 연산을 잊으면 안된다.

풀이

해결전략에 다 써놓았다.

코드

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
#include <bits/stdc++.h>
using namespace std;

int dp[1001];
int n, mod = 10007;

int solve(int n) {
    for (int i = 2; i <= n; ++i) {
        dp[i] = (dp[i - 1] + dp[i - 2] * 2) % mod;
    }
    return dp[n];
}

void input() {
    dp[0] = 1;
    dp[1] = 1;
    cin >> n;
}
int main()
{
    ios_base::sync_with_stdio(false);
    freopen("input.txt", "r", stdin);
    cin.tie(NULL);  cout.tie(NULL);

    input();
    cout << solve(n);
    return 0;
}

피드백

DP는 많은 유형을 접해보는게 답인거 같다.