[백준 11727번] - 2xn 타일링 2(C++)

11727번: 2×n 타일링 2

[문제 설명]

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

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

출력

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

예제 입력 1 복사

2

예제 출력 1 복사

3

예제 입력 2 복사

8

예제 출력 2 복사

171

예제 입력 3 복사

12

예제 출력 3 복사

2731

---

[문제 풀이]

백준 11726 2xn 타일링 문제와 거의 비슷하다.

혹시라도 안풀어봤다면 페이지 맨 아래 링크에 들어가서 문제 한번 풀어보고 오는것을 추천한다.

이 문제 역시 규칙을 찾아서 점화식을 세우면 되는 문제다.

11726 문제와 다른 점은 2x2타일이 하나 추가된 점이다.

그외에는 문제풀이는 거의 비슷하다.

 

n = 1 일때 2x1 타일 하나 두는 방법 1가지 밖에 없다.

n = 2 일때 2x1 2개, 1x2 2개, 2x2 1개를 두는 방법 3가지가 있다.

 

n = 3 일때 부터가 중요하다.

n = 1 일때에 남은 2칸을 채우는 방법 - 1칸을 채우는 경우에서 총 3가지(2x1 2개, 1x2 2개, 2x2 1개)가 있다.

n = 2 일때에 남은 1칸을 채우는 방법 - 2칸을 채우는 경우에서 총 1가지(2x1 1개)가 있다.

 

하지만, 중복되는 경우가 있다.

n-2일때 2x1 2개를 채우는 경우와

n-1일때 2x1 1개를 채우는 경우가 중복된다.

 

따라서 n-2일때 2x1 2개를 채우는 경우를 제외한 1x2 2개, 2x2 1개를 채우는 경우만 고려하면 된다.

n = 3 일때

n - 1 의 경우는 2x1 1개를 채우는것 밖에 없으니 n = 2 일때와 같고,

n - 2 의 경우는 2x2 1개, 1x2 2개를 채우는 경우 n = 1 일때에 2배가 된다.

 

위와 같은 규칙을 식으로 세우면

 

n = n - 1 + (n - 2) * 2 와 같이 세울 수 있겠다.

 

파이팅 !

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

더보기

#include <iostream>
#include <vector>
using namespace std;

int dp[1001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    dp[1] = 1;
    dp[2] = 3;
    for(int i =3; i <=n; i++)
    {
        dp[i] = dp[i-1] + dp[i-2]*2;
        dp[i] = dp[i] % 10007;
    }

    cout << dp[n] << "\n";
}

 

 

11726번: 2×n 타일링

문제 해설은 아래에 있다

백준 11726번: 2xn 타일링