[BOJ] DP 11726번 & 11727번 2xn 타일링 C++

11726번 2xn 타일링

📝문제링크 : www.acmicpc.net/problem/11726

색칠된 부분이 n-1 또는 n-2번째 블록을 그대로 표시한 것이다

점화식 : $ dp[n] = dp[n - 1] + dp[n - 2] $

소스코드

#include <iostream>
#include <vector>
using namespace std;

void	find_ans(int n, vector<int> &dp)
{
    dp[n] = (dp[n - 1] + dp[n - 2]) % 10007;
}

int     main()
{
    int		n;
    cin		>> n;

    vector<int> dp(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        find_ans(i, dp);
    }
    cout << dp[n] << '\n';
    return 0;
}

 

11727번 2xn 타일링 2

📝문제링크 : www.acmicpc.net/problem/117267

점화식 : $ dp[n] = dp[n - 1] + dp[n - 2] * 2$

소스코드

#include <iostream>
#include <vector>
using namespace std;

void	find_ans(int n, vector<int> &dp)
{
    dp[n] = (dp[n - 1] + dp[n - 2] * 2) % 10007;
}

int main()
{
    int		n;
    cin		>> n;

    vector<int> dp(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        find_ans(i, dp);
    }
    cout << dp[n] << '\n';
    return 0;
}

 

---

10007로 나눈 나머지를 저장하는 것에 대하여.

이 문제의 입력값의 범위는 1 ≤ n ≤ 1,000 이다.

(백준 질문게시판 피셜 n = 1000일 때 답 👇)
7033036771142281582183525487718354977018126983635873274260490508715453711819693357974224949456261173348
7750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403
501

int를 비롯한 숫자 자료형에 담기 어려운 큰 수라는걸 알 수 있다.

즉, 연산 중 또는 최종 결과값에서 오버플로우가 발생하기 때문에 10007으로 나눈 결과를 저장해 채점하는 것이고, 

수학적인 증명으로 단계마다 %10007을 하는 것과 마지막에 %10007을 하는 것의 결과가 똑같음을 증명할 수 있다고 한다.

나머지 연산의 분배법칙을 생각하면 편할 것 같다. 

 

( a + b) % c = ( ( a % c ) + ( b % c ) ) % c

쉬운 예로, 10진수의 수에서 일의 자리만 구하는 경우를 생각해보시면 됩니다. 덧셈과 곱셈만으로 이루어진 연산들에서 10의 자리를 넘어가는 건 아무 의미가 없으니, 매 연산마다 그 1의 자리 하나만 추적하고 있어도 결과는 똑같이 나옵니다. 마찬가지로, 이 수를 10007진수라고 생각하고 끝자리 한 자리만 추적해도 결과는 같습니다.

 

10007 이라는 숫자가 선택된 기준은 두가지 이다.

1. 실제 결과값에 대한 나머지 연산을 오버플로우 없이 잘 처리할 수 있는 적당한 크기의 수일 것 

2. 소수(Prime Number)일 것 

계산 중에 숫자가 나누어 떨어져 0이 되어버리면 안되니까 소수로 나누어준다.

그리고 $2^{30}$ 보다 작은 소수면 int값 범위 내에서 오버 플로우 없이 값을 잘 처리할 수 있다고 한다.  

 

 

 

 

참고

www.geeksforgeeks.org/modulo-1097-1000000007/

Modulo 10^9+7 (1000000007) - GeeksforGeeks