Baekjoon 11727번 2xn 타일링 2

문제

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

걸린 시간

00 : 44 : 40

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n;
int cache[1001];

int dp(int sum){
    // 기저 사례
    if(sum == n)
        return 1;
    if(sum > n)
        return 0;
    // 메모이제이션
    auto& ret = cache[sum];
    if(ret != -1)
        return ret;
    // 재귀 호출
    return ret = (dp(sum+1)+dp(sum+2)+dp(sum+2))%10007;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    memset(cache, -1, sizeof(cache));
    cout << dp(0) << "\n";
    return 0;
}

11726번 2xn 타일링 에서 2x2 도형이 하나 더 추가된 문제이다.

도형의 모양이 달라졌다고 해서 가로로 눕혀진 1x2 타일 두개와 다를 게 없는 것 같아 길이가 2 증가하는 순환 호출을 하나 더 추가했다.

예제 입력이 모두 정상적으로 작동하여 문제없이 코드를 제출하였지만 틀렸습니다 가 출력되었다.

원인은 기하급수적으로 증가하는 방법의 수로 인한 산술 오버플로에 있었다. 이를 해결하기 위한 문제의 장치로 10,007 로 나눈 나머지를 출력하라는 조건이 있다.

지난 문제는 시스템 메모리를 다 사용하지 않는 한 정수 표현에 제한이 없는 파이썬으로 풀이했기 때문에 이와 같은 문제를 전혀 고려하지 않아도 됐지만 C++ 로 풀 땐 중간 계산마다 10,007 로 나누어 주어야 한다.