백준 1793번 타일링

문제 링크입니다: https://www.acmicpc.net/problem/1793

http://jaimemin.tistory.com/401와 똑같은 문제였지만 모듈러 연산을 하는 대신 해당 경우의 수를 전부 출력해야했기 때문에 까다로운 문제였습니다.

테스트 케이스 N=100, 200은 long long 자료형으로도 커버가 안되는 숫자이기 때문에 직접 string으로 구현해야하는 문제였습니다.

밑변이 2인 사각형(2*2, 2*1) 두 가지, 밑변이 1인 사각형(1*2) 한 가지가 있기 때문에 string끼리 더하는 함수를 구현한 다음 bigNumAdd(bigNumAdd(cache[i - 2], cache[i - 2]), cache[i - 1])를 호출하여 모든 경우를 계산하면 되는 문제였습니다.

주의할 점은 2가지입니다.

1. 1의 자리부터 저장하기 때문에 마지막에 reverse 함수를 통해 합이 저장되어있는 문자열을 뒤집어줘야합니다.

2. N을 몇번 입력받는다는 얘기가 없기 때문에 while(~scanf("%d", &N)으로 처리해줘야합니다. 

#include <iostream>

#include <string>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 250 + 1;

 

int N;

string cache[MAX];

//long long int cache[MAX];

 

 

/*

long long int tiling(int width)

{

        //기저 사례: width가 1 이하일 때

        if (width <= 1)

                 return 1;

       

        long long int &result = cache[width];

        if (result != -1)

                 return result;

       

        //밑변이 2인 경우(2*2, 2*1) + 밑변이 1인 경우(1*2)

        result = tiling(width - 2) * 2 + tiling(width - 1);

        return result;

}

*/

 

//long long 자료형으로도 커버 안되는 숫자는 string으로 직접 구현해줘야한다

string bigNumAdd(string num1, string num2)

{

        long long sum = 0;

        string result;

 

        //1의 자리부터 더하기 시작한다

        while (!num1.empty() || !num2.empty() || sum)

        {

                 if (!num1.empty())

                 {

                         sum += num1.back() - '0';

                         num1.pop_back();

                 }

                 if (!num2.empty())

                 {

                         sum += num2.back() - '0';

                         num2.pop_back();

                 }

                 //다시 string 형태로 만들어 push_back

                 result.push_back((sum % 10) + '0');

                 sum /= 10;

        }

        //1의 자리부터 result에 넣었으므로 뒤집어줘야한다

        reverse(result.begin(), result.end());

        return result;

}

 

int main(void)

{

        //아무것도 안하는 것도 하나의 방법, 밑변이 1인 사각형(1*2) 한 가지

        cache[0] = cache[1] = '1';

 

        //밑변이 2인 사각형(2*2, 2*1) 두 가지, 밑변이 1인 사각형(1*2) 한 가지

        for (int i = 2; i <= 250; i++)

                 cache[i] = bigNumAdd(bigNumAdd(cache[i - 2], cache[i - 2]), cache[i - 1]);

 

        while (~scanf("%d", &N))

        {

                 cout << cache[N] << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~