1793-타일링

www.acmicpc.net/problem/1793

1793번: 타일링

간단한 DP 알고리즘으로 풀리는 문제입니다.  그런데, C++ 의 기본 정수 자료형(int, long long, unsigned long long 등)을 사용하여 다룰 수 있는 값보다 처리되는 값의 크기가 크다는 문제가 있었습니다. 이러한 큰 수를 처리할 수 있도록 string 자료형을 사용하였고, 연산 과정은 string 으로 표현된 10진 숫자를 Digit 단위로 접근하여 더하는 식으로 구현하였습니다.

 

주의할 점으로 2x0 직사각형을 채우는 방법의 수를 1로 두고 문제를 풀어야 합니다.

 

코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string dp[251];

string add_big_number(string num1, string num2)
{
    string result;

    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());

    //처리하기 용이하도록 num1 의 자리수가 num2 의 자리수보다 크거나 같도록 Swap
    if(num1.size() < num2.size()) swap(num1, num2);
    
    int carry = 0;
    for(int i = 0; i < num1.size(); i++)
    {
        int num1_digit = int(num1[i]-48);
        int num2_digit = (i < num2.size())?int(num2[i]-48):0;
        int result_digit = num1_digit + num2_digit + carry;
        carry = int(result_digit >= 10);

        if(carry) result_digit -= 10;
        result_digit = result_digit;

        result.push_back(char(result_digit+48));
    }
    if(carry) result.push_back(char(1+48));
    
    reverse(result.begin(), result.end());
    return result;
}

int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);
    // freopen("1793.txt", "r", stdin);

    dp[0] = "1";
    dp[1] = "1";
    dp[2] = "3";

    for(int i = 3; i <= 250; i++)
    {
        dp[i] = add_big_number(dp[i-1], add_big_number(dp[i-2], dp[i-2]));
    }

    int n;
    while (scanf("%d", &n) == 1) 
    {
        cout << dp[n] << '\n';
    }
    return 0;
}