백준 11726 - 2 x n 타일링 (c+

문제 설명

 

 

 

 

 

 

=> DP 문제이다. 

=> 2 x n 크기의 사각형이 있을 때, 맨 오른쪽에 타일을 채워 넣는 경우를 생각해보자.

 

 

 

그림 설명

1.  ( 2x 1 ) 타일이 세로로 세워져 있는 경우 

2. (2 x 1 ) 타일이 가로로 두개 놓여 있는 경우 

 

 

 

=> 위의 경우를 보고 점화식을 세울 수 있다. 

 

 

 

 

 

 

* arr[i] : i 크기의 사각형이 있을 때 타일을 놓을 수 있는 방법의 배열

arr [ i ] = arr [ i -1 ] + arr[ i -2 ]

 

 

 

 

 

 

 

=> 위의 점화식을 사용하여 간단하게 구현가능하다. 

=> 초기배열값은 넣어주어야 한다. 

=> arr[1] = 1, arr[2] = 2

=> arr에 넣을때 10007로 나눠주지 않으면 int의 범위를 벗어나는 일이 생긴다. 배열에 값을 넣으면서 나눠서 넣어주도록 해야 한다. 

 

 

 

 

 

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N;
    cin >> N;
   
    int arr[1001]={0,};
    
    arr[1]=1;
    arr[2]=2;
    if(N >=3)
    {
    for( int i=3; i<=N; i++)
    {
        arr[i]=(arr[i-1] + arr[i-2]) % 10007;
    }
    }
    cout <<arr[N]  <<'\n';;
    return 0;
}

 

 

 

 

 

 

 

 

 

 

실행 화면

실행 화면 2