Boj 10802) 369 놀이

문제

백준 10802

풀이 1

설명

369 게임은 3의 배수 또는 3/6/9 를 포함하는 수에서 박수를 친다.

우선 3의 배수 여부를 어떻게 구할지 생각해보자. 주어진 숫자의 범위가 크므로 에라토스테네스의 체처럼 배열을 사용할 수 없다. 대신 3의 배수는 각 자리수의 합이 3으로 나누어 떨어지는 속성을 이용해 DP 를 사용할 수 있다.

i = 자리수
j = 가장 높은 자리의 수
for(int k = 0; k < 9; k++)
{
	dp[i+1][j][0] += dp[j][k][(0 - j) MOD 3]
	dp[i+1][j][1] += dp[j][k][(1 - j) MOD 3]
	dp[i+1][j][2] += dp[j][k][(2 - j) MOD 3]
}

여기서 3/6/9 를 포함하는 경우를 제외시키는 것은 간단하다. 또한 각 자리수마다 숫자의 갯수는 일정하므로 여집합을 이용하면 3/6/9 가 포함되는 경우를 바로 구할 수 있다.

예를들어 dp[자리수][가장높은자리의 수][각 자리 수 합 MOD 3] = 인 경우의 수 에서 dp[1][1] 를 생각해보자. 1 로 시작하는 2자리 수 중에서 3이 들어가는 것을 뺀 10, 11, 12, 14, 15, 17, 18, 19 를 각 자리 수 합에 맞게 카운팅을 하면 1, 3, 3 이 된다. 전체 수는 10 개이므로 10 - 1 - 3 - 3 하면 3/6/9 가 포함되는 경우를 구할 수 있다.

이제 각 자리수마다 이를 이용해 계산하면 된다. 이때 틀리기 쉬운 부분이 a~b 범위에서 a 가 박수치는 수인 경우 따로 처리해줘야 한다는 점이다.

시간 복잡도

O(\(\mathrm{N}\))

코드

const int MOD = 20150523;
int dp[100001][10][3]; // 369 포함하지 않는 경우. DP[자리수][맨앞자리][자리수합 MOD 3]
int po10[100001];

void DP()
{
	po10[0] = 1;
	for (int i = 0; i < 100001; i++) po10[i + 1] = po10[i] * 10 % MOD;

	for (int i = 0; i < 10; i++)
		if (i % 3 != 0 || i == 0) dp[0][i][i % 3] = 1;
	for (int i = 1; i < 100001; i++)
		for (int front1 = 0; front1 < 10; front1++)
			for (int front2 = 0; front2 < 10; front2++)			
				if (front1 % 3 == 0 && front1 != 0) {
					dp[i][front1][0] = (dp[i][front1][0] + dp[i - 1][front2][(12 - front1) % 3]) % MOD;
					dp[i][front1][1] = (dp[i][front1][1] + dp[i - 1][front2][(13 - front1) % 3]) % MOD;
					dp[i][front1][2] = (dp[i][front1][2] + dp[i - 1][front2][(14 - front1) % 3]) % MOD;
				}			
}

int Solve(const string& in)
{
	int sumMod3 = 0;
	bool has3 = false;
	int res = 0;

	for (int i = 0; i < in.size(); i++)
	{
		int th = in.size() - i - 1;
		for (int j = 0; j < in[i] - '0' + (in.size() == i + 1); j++)
		{
			// 3/6/9 가 없으면서 3의 배수인 갯수
			if (has3)
			{
				res = (res + dp[th][j][0]) % MOD;
				res = (res + dp[th][j][1]) % MOD;
				res = (res + dp[th][j][2]) % MOD;
			}
			else
				res = (res + dp[th][j][(30 - sumMod3) % 3]) % MOD;

			// 3/6/9 를 포함하는 경우
			int n369 = (po10[th] - (dp[th][j][0] + dp[th][j][1] + dp[th][j][2]) + 3 * MOD) % MOD;
			res = (res + n369) % MOD;
		}
		sumMod3 = (sumMod3 + (in[i] - '0')) % 3;
		has3 |= in[i] != '0' && (in[i] - '0') % 3 == 0;
	}

	return res;
}

bool Check(const string& in)
{
	bool has3 = false;
	int sum3 = false;
	for (auto c : in)
	{
		has3 |= c == '3' || c == '6' || c == '9';
		sum3 += c - '0';
	}
	return has3 || sum3 % 3 == 0;
}

int main(void)
{
	DP();

	string a, b; cin >> a >> b;
	cout << (MOD + Solve(b) - Solve(a) + Check(a)) % MOD;
}

풀이 2

설명

풀이 1에서 최적화 할 부분이 하나 있다. 위 풀이에서 가장 높은 자리의 숫자가 다르더라도 MOD 3 이 같으면 dp 값이 같다. 그래서 dp[자리수-1][각 자리 수 합 MOD 3] = 인 경우의 수 로 두고 첫번째 자리의 숫자를 알면 기존과 같은 작업을 할 수 있다.

예를 들어 2자리 숫자이고 첫번째 자리의 수가 2 라면 dp[1][1] = 3 가 3/6/9 를 포함하지 않는 3의 배수의 갯수가 된다. 1자리 숫자이고 첫번째 자리 수가 3 이라면 dp[0][0] = 1 이 3/6/9 를 포함하지 않는 3의 배수의 갯수가 된다.

코드

const int MOD = 20150523;
int dp[100001][3]; // 369 포함하지 않는 경우, 자리수합 mod 3
int po10[100001];

void DP()
{
	po10[0] = 1;
	for (int i = 1; i < 100001; i++) po10[i] = po10[i-1] * 10 % MOD;
	
	dp[0][0] = 1;
	for (int i = 1; i < 100001; i++)
	{
		dp[i][0] = (dp[i][0] + dp[i-1][0] + 3*dp[i-1][1] + 3*dp[i-1][2]) % MOD;
		dp[i][1] = (dp[i][1] + 3*dp[i-1][0] + dp[i-1][1] + 3*dp[i-1][2] ) % MOD;
		dp[i][2] = (dp[i][2] + 3*dp[i-1][0] + 3*dp[i-1][1] + dp[i-1][2] ) % MOD;
	}
}

int Solve(const string& in)
{
	int sumMod3 = 0;
	bool has3 = false;
	int res = 0;

	for (int i = 0; i < in.size(); i++)
	{
		int th = in.size() - i - 1;
		for (int j = 0; j < in[i] - '0' + (in.size() == i + 1); j++)
		{
			// 3/6/9 가 없으면서 3의 배수인 갯수
			if (j == 0 || j % 3 != 0)
			{
				if (has3)
				{
					res = (res + dp[th][0]) % MOD;
					res = (res + dp[th][1]) % MOD;
					res = (res + dp[th][2]) % MOD;
				}
				else
					res = (res + dp[th][(30 - sumMod3 - j) % 3]) % MOD;
			}

			// 3/6/9 를 포함하는 경우
			int n369 = po10[th];
			if (j == 0 || j % 3 != 0)
				n369 += 3 * MOD - (dp[th][0] + dp[th][1] + dp[th][2]);
			res = (res + n369) % MOD;
		}
		sumMod3 = (sumMod3 + (in[i] - '0')) % 3;
		has3 |= in[i] != '0' && (in[i] - '0') % 3 == 0;
	}

	return res;
}

int main(void)
{
	DP();

	string a, b; cin >> a >> b;
	cout << (MOD + Solve(b) - Solve(a) + Check(a)) % MOD;
}