[백준 20500] Ezreal 여눈부터 가네 ㅈㅈ (C++)

문제

---

욱제는 15라는 수를 굉장히 싫어한다. 그래서 0으로 시작하지 않고 1과 5로만 구성된 N자리 양의 정수 중에서, 15의 배수가 몇 개인지 궁금해졌다.

참가자 여러분도 궁금하지요?

안 궁금함? 15ㄱ

 

입력

---

 N이 주어진다.

 

출력

---

문제의 답을 1 000 000 007로 나눈 나머지를 출력한다.

제한

---

 1 ≤ N ≤ 1515

 

문제 풀이

---

 dp 문제.

 

15로 나누어 떨어지려면 5로 나누어 떨어져야 하고, 3으로도 나누어 떨어져야 한다. 따라서 맨 마지막 자릿수는 5 고정이고, 모든 자릿수의 합이 3의 배수여야 한다.

dp를 이용하여 i자리 자릿수 중 3으로 나누었을 때 나머지가 0, 나머지가 1, 나머지가 2인 수의 개수를 구한다. i-1자리 자릿수에 1 또는 5를 붙여 i자리 자릿수를 만든다. 1은 나머지가 1추가 되고, 5는 나머지가 2 추가된다. 따라서 i자리 자릿수에서 나머지가 0인 수의 개수는 i-1자리 자릿수에서 나머지가 1인 수 + i-1자리 자릿수에서 나머지가 2인 수이다. 마찬가지로 i자리 자릿수에서 나머지가 1인 수와 2인 수의 개수는 각각 ( i-1자리 자릿수에서 나머지가 0인 수 + i-1자리 자릿수에서 나머지가 2인 수), ( i-1자리 자릿수에서 나머지가 1인 수 + i-1자리 자릿수에서 나머지가 0인 수)가 된다.

 

아래는 코드.

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	long long** dp = new long long*[N + 1];
	for (int i = 0; i < N + 1; i++)
	{
		dp[i] = new long long[3];
		for (int j = 0; j < 3; j++)
		{
			dp[i][j] = 0;
		}
	}
	dp[1][0] = 0;
	dp[1][1] = 0;
	dp[1][2] = 1;
	for (int i = 2; i < N + 1; i++)
	{
		dp[i][0] = (dp[i-1][2] + dp[i-1][1]) % 1000000007;
		dp[i][1] = (dp[i-1][2] + dp[i-1][0]) % 1000000007;
		dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 1000000007;

		dp[i][0] %= 1000000007;
		dp[i][1] %= 1000000007;
		dp[i][2] %= 1000000007;
	}
	cout << dp[N][0] << "\n";
	return 0;
}