[백준/c++] 11726번: 2xn 타일링

 

 

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

11726번: 2×n 타일링

 

문제 요약

 

2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하라.

(1 ≤ n ≤ 1,000)

 

출력 형태

 

방법의 수를 10007로 나눈 나머지를 출력한다.

 

 

---

 

 

문제를 보면 주어진 n에 대해서 2xn 타일링 경우의 수를 구하는 것이다. 이를 작은 문제를 분해해보자.

2xi 타일을 채울 수 있는 방법의 수를 구해서 점점 값을 올려 2xn을 타일로 채울 수 있는 경우의 수를 구할 수 있을 것 같다.

 

i = 1의 경우, 2x1 타일 하나 → 1

i = 2 의 경우, 2x1 타일 2개 또는 1x2 타일 2개 → 2

i = 3 의 경우, 2x1 타일 3개 또는 1x2 타일 2개/2x1 타일 1개 또는 2x1 타일 2개/1x2 타일 1개 → 3

i = 4 의 경우, 2x1 타일 4개 또는 1x2 타일 4개 또는 1x2 타일 2개/2x1 타일 2개인 3가지 경우 → 5

...

 

규칙이 보인다. i-1, i-2의 경우의 수를 더하면 된다. 대신, 1과 2의 경우는 1, 2로 고정한다.

#include <iostream>
#define NUM 1002
using namespace std;
int Dy[NUM], n;

void solution(){
    Dy[1] = 1; Dy[2] = 2;

    for(int i=3; i<=n; i++){
        Dy[i] = (Dy[i-1] + Dy[i-2]) % 10007 ;
    }
    
    cout << Dy[n] << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    solution();
    return 0;
}

 

 

 

값에 % 10007를 하는 것을 빼먹어서 한번 틀렸다..🥲

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!