[백준 20500] Ezreal 여눈부터 가네 ㅈㅈ

다이나믹 프로그래밍 문제

www.acmicpc.net/problem/20500

친숙한 문제입니다.

---

[문제 풀이]

 

1과 5로만 주어진 N자리 자연수 중 15의 배수의 개수를 찾는 문제입니다.

15의 배수라고 하니 별다른 특징을 찾기가 힘듭니다. 조금 형태를 바꿀 필요가 있어 보입니다.

 

15는 3의 배수이면서 5의 배수입니다. 

3과 5는 배수를 구할 때 상당히 익숙한 수입니다.

그러므로 15의 배수인 수를 구하기 위해 3의 배수이면서 5의 배수인 수를 구해보겠습니다.

 

우선 3의 배수는 모든 자리의 수를 전부 더하고 3으로 나눴을 때 나누어 떨어지는 성질이 있습니다.

그리고 5의 배수는 1의 자릿수가 0이거나 5입니다.

이 문제에서는 1과 5로만 수가 이루어져 있으므로 1의 자릿수가 5입니다.

 

그러므로 15의 배수는 모든 자리의 수를 전부 더한 값을 3으로 나눴을 때 나누어 떨어지면서, 1의 자리수가 5인 수입니다.

 

 

15의 배수는 어떻게 구하는지 찾았습니다.

문제는 15의 배수를 어떻게 빠르게 찾는지입니다.

 

1과 5로 이루어진 N자리의 모든 자연수를 확인하는 것은 $O(2^N)$의 시간 복잡도를 갖습니다.

N의 제한이 1515이므로 빠르게 포기합시다.

 

여기서 빠르게 N자리 자연수들을 확인하기 위해 다이나믹 프로그래밍이 사용됩니다.

1의 자릿수를 5로 고정시키고, 한 자리씩을 늘려가면서 3으로 나눈 나머지 값이 0, 1, 2인 것이 각각 몇 개 있는지 기록하는 것이 핵심 아이디어입니다.

dp테이블은 2차원이고 dp[3][N]으로 설정하겠습니다.

dp[i][j]라고 하면 j자리이면서 3으로 나눈 나머지가 i인 수의 개수를 나타냅니다.

 

dp를 사용하기 위해서는 초기값 설정이 중요합니다. 초기값부터 설정하겠습니다.

1자리 수 중 15로 나눠지는 수는 없으므로 초기값 설정에 큰 도움이 되지 않습니다.

2자리 수로 초기값을 잡겠습니다.

 

1의 자리가 5로 고정되어 있으므로 2자리 수의 조합은 15와 55만 가능합니다.

15를 3으로 나눈 나머지가 0이므로 dp[0][2] = 1, 55를 3으로 나눈 나머지가 1이므로 dp[1][2] = 1, dp[2][2] = 0입니다.

이제 한 자리씩 늘려가면서 dp테이블을 채우겠습니다.

 

dp[0][2] = 1이므로 dp[(0 + 1) % 3][3]도 1을 더하고, dp[(0 + 5) % 3][3]도 1을 더합니다.

실제로 생각해보면 dp[0][2]는 15이고, 15에 한 자리를 추가한 115와 515는 나머지가 각각 1과 2입니다.

위에서 dp[1][3]과 dp[2][3]에 1이 더해졌으니 dp테이블에 올바르게 기록된 것을 확인할 수 있습니다.

 

즉, dp[(i + 1) % 3][j] += dp[i][j - 1], dp[(i + 5) % 3][j] += dp[i][j - 1]처럼 계속 진행하고 dp[0][N]를 출력하면 답을 구할 수 있습니다.

$(A_1 + A_2 + ... + A_n) \ \% \ p = (A_1 \ \% \ p + A_2 \ \% \ p + ... + A_n \ \% \ p) \ \% \ p$ 이므로 위처럼 진행해도 문제가 없습니다.

 

이런 방식으로 N자리까지 dp를 진행하면 $O(N)$의 시간 복잡도로 해당 문제를 해결 가능합니다.

 

---

[소스 코드] / C++

 

위에서 서술한 점화식을 사용해도 되지만 약간의 변형을 거쳐 아래 코드의 형태로 바꿀 수 있습니다.

MOD연산이 익숙하다면 금방 아래 코드의 점화식을 도출할 수 있을 겁니다.

 

#include <iostream>
#include <vector>

using namespace std;

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

	int N, MOD = 1'000'000'007;
	cin >> N;

	int dist[3][1516];
	dist[0][1] = 0;
	dist[0][2] = 1; dist[1][2] = 1; dist[2][2] = 0;

	for (int i = 3; i < N + 1; i++) {
		dist[0][i] = (dist[2][i - 1] + dist[1][i - 1]) % MOD;
		dist[1][i] = (dist[0][i - 1] + dist[2][i - 1]) % MOD;
		dist[2][i] = (dist[1][i - 1] + dist[0][i - 1]) % MOD;
	}

	cout << dist[0][N];

	return 0;
}