문제 링크입니다: 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
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 4108번 지뢰찾기 (0) | 2018.06.28 |
---|---|
백준 9184번 신나는 함수 실행 (4) | 2018.06.28 |
백준 5719번 거의 최단 경로 (7) | 2018.06.27 |
백준 5214번 환승 (0) | 2018.06.27 |
백준 1058번 친구 (6) | 2018.06.27 |