[Algorithm]Baekjoon 20500번 :: Ezreal 여눈부터 가네 ㅈㅈ

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

 

#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;
 
const int mod = 1000000007;
int n;
int dp[1516][3] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    dp[2][0] = dp[2][1] = 1;
    
    for (int i = 3; i <= n; ++i)
    {
        dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % mod;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
    }
 
    cout << dp[n][0];
}
 
 
 

 

 

수의 규칙을 파악해야하는 정수론문제이다.

15의 배수인 숫자를 모두 찾아야하는데, 15를 구성하는 소수(PrimeNum)인 3과 5는 다음과같은 규칙을 가지고있다고 한다.

 

1.     3의 배수인 숫자는, 모든 자릿수를 더했을 때 3으로 나누어떨어진다.

2.     5의 배수는 1의자리수가 반드시 0 or 5 이다.

 

이 문제에서는 15의 배수를 구하여야 한다.

15의 배수인 숫자는 곧 3의배수인 숫자이니, 15의배수인 숫자의 모든자릿수를 더했을 때 반드시 3으로 나누어떨어져야 한다.

그리고 붙여나가는 숫자는 1과 5밖에 없으니, 1의자리수는 반드시 5여야 한다. 

 

자 그러면 매번 숫자를 1이나 5를 붙여나갈건데, 숫자를 붙였을 떄 이 숫자가 15의배수인지 어떻게 판단할 것인가?

간단하게 생각하면 그냥 매번 자리수 붙인다음, 정수형으로 변경하고 % 15 == 0일 경우 카운팅하면 될 것 같지만, 자리수는 최대 1515자리이기 때문에 정수형으로 변경이 불가능하다. (숫자가 너무커서 메모리에 담을수없다)

 

혹은 숫자를 문자열로 만든 후, 매번 1이나 5를 붙이면서 자리수를 전부 채웠을 때, 해당 숫자문자열의 길이만큼 반복문 돌아서 자리수를 전부 더한 후, 3으로 나누어떨어지는지 검사하는 방법도 있다.

다만 이 경우도 시간이 오래 걸린다. 숫자가 완성되는 경우의 수가 너무 많다.

 

우리는 최종적으로 3으로 나누어떨어지는 수를 구하면되니, 이전의 값들을 이용해 이 수를 구하는것을 생각해보자.

모든 자리수를 더했을 떄 3으로 나누어 떨어진다... 라는것은 만약 이전숫자가 3으로 나눴을 때 나머지가 1이라면,  우리는 여기다가 5를 붙일경우, 3으로 나눴을 때 0으로 나누어떨어진다.

 

왜? 이전숫자까지 나머지가 1인데, 5를 붙일경우 5는 3으로나눴을 때 나머지가 2이다.

그렇기때문에 나머지가 1인상태에서 나머지가 2인 숫자를 붙였으니, 결국 나머지가 3이되니 3으로 나눴을 때 0이 된다!

 

마찬가지로 이전숫자까지 나머지가 2일경우 숫자 1을붙이면, 즉 나머지가 1인 숫자를 붙이면 나머지가 3이되니 3으로 나눴을 때 0이 된다.

 

그렇기때문에 이런 점화식이 성립한다.

dp[i][j] 는 i번째까지 숫자를 구성후 3으로 나눴을때 나머지가 j인 숫자의 개수..이다.

 

i는 인덱스이니 최대 n이되고 j는 나머지가 0,1,2인 경우를 모두 들고있어야하니 각 종류의개수인 3이 된다.