백준 2378: 불필요한 수

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

 

비록 골드 3의 난이도지만, 이 문제를 풀기 위해서, 하루이틀 동안 많은 생각을 했고 드디어 스스로 해결을 하였다.

많은 시도를 한 문제지만 처음엔 그냥 단순하게 생각했다. 아무 생각없이, 각 난수의 계수들은 1,2,3,4,5,6... 순서대로 올라가다, 내려가는 형태일 것이라고 생각했고, 각 계수가 M으로 나누어질 때, 그것이 답이다라 생각하며, 그냥 그대로 코드를 제출했다.

#include <iostream>
#include <vector>
using namespace std;
vector<int> ans;
int N, M, R[100001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	for (int i = 1; i <= (N / 2); i++)
		R[i] = i;
	for (int i = (N / 2) + 1; i <= N; i++)
		R[i] = N - i + 1;
	for (int i = 1; i <= N; i++)
		if (R[i] % M == 0)
			ans.push_back(i);
	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
	cout << '\n';
}

아무리 생각하기 귀찮았다하더라도 이 코드는 너무 안일했다. 당연히 틀렸고, 다시 처음부터 생각을 하였다. 일단 나는 N이 2인 경우부터 시작해서 3, 4, 5, 6 ... 인 경우의 각 난수의 계수를 메모장으로 적기 시작했다.

 

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

1 9 36 84 126 126 84 36 9 1

 

여기까지 적은 뒤, 규칙을 찾았고, 분자가 N - 1, 분모는 1부터 시작할 때, 각 수의 다음 수는 이전에 사용한 분수의 분자에 1을 빼고, 분모에 1을 더해서 곱한다란 사실을 발견했다. 그렇게 구현한 코드는 다음과 같다.

#include <iostream>
#include <vector>
using namespace std;
vector<int> ans;
long long N, M, R[100001];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	R[1] = 1;
	double s = N - 1, m = 1;
	for (int i = 2; i <= (N / 2) + (N % 2); i++, s--, m++)
		R[i] = R[i - 1] * (s / m);
	for (int i = 1; i <= N; i++)
	{
		int idx = (i > (N / 2) + (N % 2)) ? N + 1 - i : i;
		if (R[idx] % M == 0)
			ans.push_back(i);
	}
	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++) cout << ans[i] << '\n';
	cout << '\n';
}

 

여담으로 이런 규칙을 가지게 된 것은 각 난수의 계수가 이항 계수이기 때문이란 것은 뒤늦게 알게되었다.

 

이번에야말로 정답일거라 생각해서 제출을 했는데, 이번에도 틀렸습니다를 받았다. 정말 이해할 수 없어서, 큰 수로 입력을 넣고, breakpoint를 걸어본 결과, 계수가 내 생각보다 훨씬 커서, long long 타입의 범위(2 ^ 64 - 1)를 거뜬히 넘어 오버플로우가 걸린다는 사실을 발견했다.

 

결국, 이 큰 수를 어떻게 다룰 것인지가 관건이 되었다. 이것을 해결하기 위해 몇 가지 해결책을 생각했다.

첫째, 소수의 나머지로 답을 구한다. 사실 이건 딱히 근거가 있었던건 아니고, 다른 문제들에서, 큰 수를 1000000007로 나머지를 활용했기에, 한 번 시도를 해보았다. 당연히 틀렸다.

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
vector<int> ans;
ll N, M, R[100001];
const ll MOD = 1000000007;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	R[1] = 1;
	double s = N - 1, m = 1;
	for (int i = 2; i <= (N / 2) + (N % 2); i++, s--, m++)
	{
		R[i] = R[i - 1] * (s / m);
		R[i] %= MOD; // 추가
	}
	for (int i = 1; i <= N; i++)
	{
		int idx = (i > (N / 2) + (N % 2)) ? N + 1 - i : i;
		if (R[idx] % M == 0)
			ans.push_back(i);
	}
	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++) cout << ans[i] << '\n';
}

둘째, 각 계수를 M의 나머지를 활용해 구한다. 이건 근거가 없는 것은 아니였다.

모듈러 분배 법칙 중에, 곱셈의 각 피연산자에게 모듈러 연산을 하고, 곱한 뒤, 모듈러 연산을 할 수 있기 때문에, 이전의 값과, 곱할 분수에 나머지를 구해 곱하면 된다. 란 생각이다.

(a * b) % M == ((a % M) * (b % M)) % M

이것을 바탕으로 구현한 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
using ll = long long;
vector<int> ans;
ll N, M, R[100001];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	R[1] = 1;
	double s = N - 1, m = 1;
	for (int i = 2; i <= (N / 2) + (N % 2); i++, s--, m++)
	{
		R[i] = (R[i - 1] % M) * fmod((s / m), M);
		R[i] = R[i] % M;
	}
	for (int i = 1; i <= N; i++)
	{
		int idx = (i > (N / 2) + (N % 2)) ? N + 1 - i : i;
		if (R[idx] == 0)
			ans.push_back(i);
	}
	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++) cout << ans[i] << '\n';
}

fmod는 실수의 나머지 연산을 할 때 사용하는 메소드이다.

드디어 정답일까? 정말로 안타깝게도 아니다. 왜냐하면, 이 모듈러 분배 법칙은 두 피연산자가 정수일 때 통한다. 나는 이것을 뒤늦게 알았다.

 

단적인 예로 이 코드는 입력값 5 3을 통과하지 못한다.

이 입력값의 난수 계수는 1 4 6 4 1인데, 중간의 나머지가 0이 되어버려서, 이 뒤의 값들이 0이 된다.

 

마지막으로, 이 뒤로는 해결책을 떠올리기 정말 힘들었지만, 계속 생각을 한 결과 드디어 하나의 해결책을 발견했다.

바로 소인수분해를 활용하는 방법이다.

 

일단 현재의 계수의 값을 표현하기 위해서 배열 하나를 준비한다. 이 배열은 현재의 값을 소인수분해한 값이다.

예를 들어서, 84란 값이 있다고 하면, (2^2 * 3 * 7)로 소인수 분해하고, 이것을 배열로 바꾸면

0 0 2 1 0 0 0 1 0 0 0 ....

이렇게 바꿀 수 있다.

 

그리고, 계수를 구하기 위해선 곱해지는, 각 분수의 분자와 분모를 각각 소인수분해하고, 분자는 더하고, 분모는 뺀다.

이제, 미리 소인수분해한 M과 비교해서, 작은 값이 하나라도 있으면 이 계수는 답이 아니고, 없으면 답이다.

소인수분해를 위해 나는 에라토스테네스의 체를 활용했고, 그렇게 나온 코드는 다음과 같다.

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

const int MAX = 100001;
int D[MAX];
vector<int> d[MAX], ans;
int N, M, c[MAX], cmp[MAX];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	memset(D, -1, sizeof(D));
	for(int i = 2; i < MAX; i++)
		if (D[i] < 0)
		{
			D[i] = i;
			for (int j = i + i; j < MAX; j += i)
				D[j] = i;
		}
	for (int i = 2; i < MAX; i++)
	{
		int num = i;
		while(num > 1)
		{
			d[i].push_back(D[num]);
			num /= D[num];
		}
	}
	cin >> N >> M;
	for (int j = 0; j < d[M].size(); j++)
		cmp[d[M][j]]++;
	double s = N - 1, m = 1;
	for (int i = 2; i <= N; i++, s--, m++)
	{
		for (int j = 0; j < d[(int)s].size(); j++)
			c[d[(int)s][j]]++;
		for (int j = 0; j < d[(int)m].size(); j++)
			c[d[(int)m][j]]--;
		bool f = true;
		for(int j = 0; j < d[M].size(); j++)
			if (cmp[d[M][j]] > c[d[M][j]])
			{
				f = false;
				break;
			}
		if (f)
			ans.push_back(i);
	}
	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
	cout << '\n';
}

제출한 뒤, 이 코드 또한 정답이 아니였다는 것을 알게되었다. 왜냐하면 M이 배열의 최대 크기인 100,000을 넘어버려서, 미리 구해놓은 소인수분해 방식을 사용할 수 없기 때문이다. 그렇기 때문에 M은 특별 취급을 해서 따로 구해야만 했다. 이것을 위해 미리 소수를 저장하고, 그 소수로 소인수분해하면 된다.

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

const int MAX = 100001;
int D[MAX];
vector<int> d[MAX], ans, P, mDiv;
int N, M, c[MAX], cmp[MAX];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	memset(D, -1, sizeof(D));
	for (int i = 2; i < MAX; i++)
		if (D[i] < 0)
		{
			D[i] = i;
			P.push_back(i);
			for (int j = i + i; j < MAX; j += i)
				D[j] = i;
		}
	for (int i = 2; i < MAX; i++)
	{
		int num = i;
		while (num > 1)
		{
			d[i].push_back(D[num]);
			num /= D[num];
		}
	}
	cin >> N >> M;
	int idx = 0;
	while (M > 1)
	{
		if (M % P[idx] > 0) ++idx;
		else
		{
			M /= P[idx];
			++cmp[P[idx]];
			if(mDiv.empty() || mDiv.back() != P[idx])
				mDiv.push_back(P[idx]);
		}
	}
	for (int j = 0; j < d[M].size(); j++)
		cmp[d[M][j]]++;
	double s = N - 1, m = 1;
	for (int i = 2; i <= N; i++, s--, m++)
	{
		for (int j = 0; j < d[(int)s].size(); j++)
			c[d[(int)s][j]]++;
		for (int j = 0; j < d[(int)m].size(); j++)
			c[d[(int)m][j]]--;
		bool f = true;
		for (int j = 0; j < mDiv.size(); j++)
			if (cmp[mDiv[j]] > c[mDiv[j]])
			{
				f = false;
				break;
			}
		if (f)
			ans.push_back(i);
	}
	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
	cout << '\n';
}

드디어 많은 시도 끝에 문제를 해결했다.. 정말 먼 길을 돌아온 기분이다. 중간에 소인수분해에 대한 답변에 자신이 없어서, 다른 곳에서 삽질을 했었고, 큰 수 나머지, 이항 계수 나머지 등을 구글링 하며, 어떻게 적용을 할 지 고민을 하는 등의 많은 시간을 소모했으니 더더욱...