[DP] 2*N 타일링

문제

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

11726번: 2×n 타일링

2Xn크기의 직사각형을 2X1, 1X2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래는 2X5의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

 

출력

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

 

---

풀이

1.일단 n이 1과 2일 때 경우의 수를 구해본다

 

 

n이 1일 경우는 2*1로 채우는 방법 1

n이 2일 경우는 2*1로 채우거나, 1*2로 채우는 방법 2

 

 

2.이때부터 n이 얼마나 증가하든 아래와 같이 생각하면 된다

- n-1의 경우의 수에 2*1 타일을 붙이는 경우

- n-2의 경우의 수에 1*2 타일을 붙이는 경우

 

무슨 소리냐면

ex. n이 3인경우

1) n이 1(3-2)일때 1*2 타일을 붙이는 경우 = 1

2) n이 2(3-1)일때 2*1 타일을 붙이는 경우 = 2 //n(2)의 경우의 수가 2이므로

 

1+2 = 3

 

ex. n이 10인 경우

n(8)에 1*2를 붙여주는 경우 + n(9)에 2*1을 붙여주는 경우가 됨

 

즉, 이전 경우의 수를 다 구해놨다는 가정하에 dp[n] = dp[n-1] + dp[n-2] 라는 식이 나온다.

 

*이렇게 DP문제를 풀 땐

1.작은 부분부터 공통된 식을 도출해내고

2.메모리제이션으로 작은 부분부터 도출해나온 값을 이용해 풀어보기

 

//사실 아직 감이 잘 잡히진 않지만 풀다보면 익숙해질듯

---

 

코드

#include <stdio.h>

int main(){
    int n;
    int dp[1001];
    
    dp[0] = 1;
    dp[1] = 1;
    
    scanf("%d",&n);
    for(int i=2; i<=n; i++){
        dp[i] = (dp[i-1] + dp[i-2]) % 10007;
    }
    
    printf("%d", dp[n]);
}