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

#문제

11726번: 2xn 타일링

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

11726번: 2×n 타일링

 

---

#접근방법

동적계획법으로 접근하였다.

반응형

---

#풀이

#include <stdio.h>

int dp[1005]={1,1};

int main(){
    int n;

    scanf("%d",&n);

    for(int i=2;i<=n;i++)
        dp[i] = (dp[i-1] + dp[i-2])%10007;

    printf("%d\n",dp[n]);

    return 0;
}

 

2xn의 직사각형이 있다고 가정을 해보자. 이 직사각형을 1x2 또는 2x1타일로 가득 채울 것이다.

 

가장 왼쪽에는 2x1타일 하나가 있거나, 1x2타일이 2개 채워져 있을 수 있다.

 

2x1타일이 채워진 경우는 공간이 2x(n-1)의 빈공간이 있을 것이며, 1x2타일이 2개 채워진 경우는 2x(n-2)의 빈공간이 있을 것이다.

 

따라서 이 두가지 경우를 더하면 2xn의 공간을 채우는 경우의 수가 된다.

 

먼저 dp배열에 초기값 1,1을 넣어준뒤 n을 입력받고 2 ~ n까지 반복문을 돌아준다.

 

10007의 나머지 값을 구하라고 문제에 나와있으므로 dp[i] = (dp[i-1] + dp[i-2])%10007로 동적계획법을 설계한다.

 

dp[n]을 출력하면 정답이다.

 

식을 세우고 보니 피보나치 수열과 똑같은 형태이다.

---

#성능

---

#정리

동적계획법으로 풀어야 한다는 것,

 

경우의 수를 식으로 만들 수 있으면 풀 수 있는 문제였다.