[백준/C++] 박성원 (No. 1086)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 매우 큰 수를 입력받아 처리를 해야하는 문제다.

 

이외에도 N이 15로 큰 값이기 때문에 (15!)을 전부 계산하면 시간 초과가 나게 된다.

 

그래서 이러한 반복을 줄이는 방법은 나머지를 이용하는 방법이다.

 

예를 들어 아래와 같은 경우를 생각해보자. 

 

그러면 17, 6 순서로 정수를 만드는 경우와 6, 17 순서로 정수를 만드는 경우는 나머지가 1로 같다.

 

이를 이용하면 176333과 617333의 나머지가 같음을 알 수 있다.

(왜냐하면 176과 617의 나머지가 1이였으므로, 333을 뒤에 붙이면 1333 이 된다. 이때, 두 수가 1333으로 같으므로 두 경우는 같은 경우다.)

 

이를 이용하면 [현재 사용한 수열의 수 집합][남은 나머지]의 2차원 vector를 이용해 빠르게 문제를 해결할 수 있다.

 

여기서 현재 사용한 수열의 집합은 bit 마스킹을 이용해 2^N의 수로 표현했다.

 

+ 추가로 고려해야하는 부분이 있다.

나머지와 N개의 수를 이용해 K로 나눈 나머지를 계속 계산하는 과정에서 시간 초과가 날 수 있다.

이 부분도 2차원 vector로 계산값을 기록해 해결할 수 있다.

[현재까지 계산된 나머지][N번째 수]로 이루어진 2차원 vector를 만들면 단순히 2차원 배열의 값을 찾는 것으로 계산을 하지 않고 이후 나머지가 얼마가 되는지 빠르게 계산할 수 있다.

(여기서 현재까지 계산된 나머지는 K로 나눈 수라서 K값 보다 작다)

 

이후 두 수를 기약분수로 만들어 주면 되는데, 기약분수로 만들어주는 과정은 GCD를 이용해 최대 공약수를 계산해 나누어 주면 된다.

 

 

​

[아이디어 정리]

1. [현재 사용한 수열의 수 집합][집합으로 수를 만든 후 남은 나머지] 의 2차원 vector를 만들어 같은 경우는 중복된 계산을 하지 않도록 한다.
2. 현재 나머지 + i번째 수로 수를 만들 경우 나머지 값을 중복해서 계속 계산하지 않도록 [현재까지 계산된 나머지][N번째 수]로 이루어진 2차원 vector를 만들고 이미 계산된 값을 이용해 계산한다.
3. 최종적으로 경우의 수가 계산되면, GCD를 이용해 최대공약수를 구하고 최대공약수로 나눈 값을 출력한다.

 

 

 

Code

 

 

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


int N, K;
vector<vector<long long>> DP;
vector<char[50]> CV;
vector<vector<int>> QUO; // [나머지][몇번째 수]

int CtoI(char &c) {
	int ret = c - '0';
	return ret;
}

int CalcNum(int quo, int cN) {
	int nNum;
	for (int i = 0; i < 50; i++)
	{
		nNum = CtoI(CV[cN][i]);
		if (nNum >= 0 && nNum <= 9) {
			quo *= 10;
			quo += nNum;
			quo %= K;
		}
		else {
			break;
		}
	}
	return quo;
}

long long DFS(int bits, int quo) {
	long long* retAns = &DP[bits][quo];
	if (DP[bits][quo] != -1) 
	{
		return DP[bits][quo];
	}

	int idx;
	DP[bits][quo] = 0;
	for (int i = 0; i < N; i++) {
		idx = 1 << i;
		if ((bits & idx) == 0) 
		{ //방문한 적이 없다면, 방문시키기
			DP[bits][quo] +=DFS(bits | idx, QUO[quo][i]);
		}
	}
	return DP[bits][quo];
}

long long GCD(long long a, long long b) {
	if (a % b == 0) {
		return b;
	}
	else {
		return GCD(b, a % b);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	CV = vector<char[50]>(N);
	for (int i = 0; i < N; i++) {
		cin >> CV[i];
	}
	cin >> K;
	// 초기화
	QUO = vector<vector<int>>(K,vector<int>(N,-1));
	for (int i = 0; i < K; i++) {
		for (int j = 0; j < N; j++) {
			QUO[i][j] = CalcNum(i, j);
		}
	}

	int maxBits = (1 << N) - 1;
	DP = vector<vector<long long>>(maxBits + 1, vector<long long>(K, -1));
	DP[maxBits][0] = 1;
	for (int i = 1; i < K; i++) {
		DP[maxBits][i] = 0;
	}
	long long G = 1;
	for (int i = 1; i <= N; i++) {
		G *= i;
	}
	if (DFS(0, 0) == 0) {
		cout << "0/1";
		return 0;
	}
	long long gcd = GCD(G, DFS(0, 0));
	cout << DFS(0, 0) / gcd << "/" << G / gcd << "\n";

	return 0;
}

 

---

처음 문제를 봤을 때, 작은 경우들 중 같은 경우가 있다는게 바로 보이지 않아 나머지를 이용할 생각이 나지 않았다.

예전부터 느꼈지만 이런 유형의 문제는 기준으로 잡을 부분이 바로 생각나면 빠르게 해결되지만, 생각이 안나면 정말 오래 걸리는 문제인 것 같다.

 

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