[Algorithm]Baekjoon 1793번 : 타일링

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

1793번: 타일링

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
 
string dp[251];
 
string Add(string num1, string num2)
{
    string smallString = num1.size() <= num2.size() ? num1 : num2;
    string bigString = num1.size() > num2.size() ? num1 : num2;
    string result = "";
    int offset = 0;
 
    for (int i = 0; i < smallString.size(); ++i)
    {
        int addedNum = (bigString[i] - '0') + (smallString[i] - '0') + offset;
        int num = addedNum % 10; // 집어넣을 숫자
        offset = addedNum / 10; // 올림수
 
        result.push_back(num + '0');
    }
 
    for (int i = smallString.size(); i < bigString.size(); ++i)
    {
        if (offset)
        {
            int addedNum = (bigString[i] - '0') + offset;
            int num = addedNum % 10;
            offset = addedNum / 10;
 
            result.push_back(num + '0');
        }
        else result.push_back(bigString[i]);
    }
 
    if (offset) result.push_back('1');
 
    return result;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    dp[0] = "1";
    dp[1] = "1";
    dp[2] = "3";
 
    for (int i = 3; i <= 250; ++i)
    {
        dp[i] = Add(dp[i - 1], Add(dp[i - 2], dp[i - 2]));
    }
 
    int n;
    while (cin >> n)
    {
        for (int i = dp[n].size() - 1; i >= 0; --i)
        {
            printf("%c", dp[n][i]);
        }
        printf("\n");
    }
}

 

타일링DP + 큰 수가 섞인 문제이다.

 

타일링DP같은 경우는 이제 경험치가 좀 쌓여서 그런가 쉽게 구했다.

 

타일이 각가 1*2, 2*1, 2*2가 주어지기 때문에, 맨 앞에 독립적으로 놓여지는 경우를 생각해보자.

 

1*2짜리를 세우던가, 2*1짜리를 두개 쌓던가, 2*2짜리를 한개 세워놓는것이다.

 

1*2짜리를 세워놨다면 한칸을 사용한것이니, 이후 dp[n-1]에 해당하는 경우를 쭉 나열하면 된다.

2*1짜리 두개를 맨 앞에 세워놨다면 두칸을 사용했기 때문에, 이후 dp[n-2]에 해당하는 경우를 쭉 나열하면 된다.

2*2짜리 한개를  맨 앞에 세워놨다면 마찬가지로 두칸을 사용했기 때문에, 이후 dp[n-2]에 해당하는 경우를 쭉 나열하면 된다.

 

그러니 점화식은 dp[n] = dp[n-1] + dp[n-2] * 2 가 된다.

 

문제는 수가 너무 커서 정수형 데이터타입에 담을 수 없으니 스트링으로 변환해서 계산해야 된다.

해당코드는 조금만 머리써서 구현하면 된다. 올림수처리만 하면 어렵지 않다.

 

사실 이 문제에서 제일 인지해야할 것은, DP[0] == 1이라는 것이다.

n값이 0일경우 1을 출력해야 한다.

아무 블럭도 세우지않는다... 라는것도 경우의 수이기 때문이다.