백준 1793: 타일링

백준
https://www.acmicpc.net/problem/1793

문제

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

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

 

 

생각

1. 아 DP다
2. 0은 0, 1은 1, 2는 3, 3은 5
3. dp[ix] = dp[ix -1] + 2 * dp[ix-2]
4. 문제는 숫자가 너무 큼 이걸 어떻게 처리해야할지 모르겠음 일단 long long 보다 큼

 

코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
   
    int n;
   
    vector<long long> dp(251);
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 3;
   
    for(int ix = 3; ix <= 250; ++ix)
    {
        dp[ix] = dp[ix-1] + 2 * dp[ix-2];
    }

    while(cin >> n)
    {
        std::cout << dp[n] << "\n";
    }
}

틀린 이유

• 역시나 걱정했던 부분의 숫자가 큰게 문제
• 아직은 준비가 안된거 같음
• 0일때 1이라고 했어야함

 

다른 분들 풀이

( 내가 푼게 최적일리가 없어 )