[Python] 백준 - 1086 박성원

문제

박성원은 이 문제를 풀지 못했다.

서로 다른 정수로 이루어진 집합이 있다. 이 집합의 순열을 합치면 큰 정수 하나를 만들 수 있다. 예를 들어, {5221,40,1,58,9}로 5221401589를 만들 수 있다. 합친수가 정수 K로 나누어 떨어지는 순열을 구하는 프로그램을 작성하시오.

하지만, 박성원은 이 문제를 풀지 못했다.

따라서 박성원은 그냥 랜덤하게 순열 하나를 정답이라고 출력하려고 한다. 이 문제에는 정답이 여러 개 있을 수도 있고, 박성원이 우연히 문제의 정답을 맞출 수도 있다.

박성원이 우연히 정답을 맞출 확률을 분수로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 집합의 수의 개수 N이 주어진다. N은 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 집합에 포함된 수가 주어진다. 각 수의 길이는 길어야 50인 자연수이다. 마지막 줄에는 K가 주어진다. K는 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다.

 

필요한 도구

 

1. 비트마스크 도구

1) bit & (1 << i) :
 
(1 << i)는 1의 $2^{i}$이고, AND 연산은 bit와 (1 << i) 둘 다 1이거나 0 일 때, 1을 출력한다.
방문여부를 체크할 때 사용된다.

 
2) bit | (1 << i) :
 
(1 << i)는 1의 $2^{i}$이고, OR 연산으로 bit와 (1 << i) 둘 중 하나가 1이면, 1을 출력한다.
방문여부를 저장할 때 사용된다.
 
3) bit == (1 << n) -1 : n = 4일 때, 01111(십진수15)이다. 모두 방문했을 경우다.

 

※ 비트마스크의 장점.

1) $O(1)$의 연산속도를 가진다.

2) 적은 메모리를 사용한다.

3) 구현된 코드가 간소함. 

 

 

2. 주어진 입력을 처리하는 자료구조

 

1) dp리스트 = [[k로 나눈 나머지] 비트배열(방문)]

dp = [[-1 for _ in range(k)] for _ in range(1 << n)]

 

2) 주어진 집합의 원소의 문자열 길이(자릿수)를 저장하는 리스트: lth

lth = [len(str(d[i])) for i in range(n)]

 

3) 주어진 집합의 원소가 각 자릿수에 위치할 때 나머지를 저장하는 리스트 : rest_box

rest_box = [[-1 for _ in range(sum(lth))] for _ in range(n)]

 

 

문제해결방법 - (서칭 참고)

 

이 문제와 비슷한데, 조금 더 자료구조 전처리가 필요한 문제이다. 1311번(할 일 정하기1) 문제는 순차적으로 남아있는 일을 배당하는 개념이고(인자가 idx+1이 된다.), 2098번(외판원 순회) 문제는 방문할 수 있는 다음 노드를 인자로 삼는다.

 

이 문제는 방문할 수 있는 노드가 위치할 "자릿수"를 누적해 반영해야 한다. (말로는 복잡해보이는데, 그렇게 복잡하지는 않다..!)

[Python] 백준 - 2098 외판원 순회

 

 

1. dfs함수에서 다음 호출되는 dfs함수의 값을 변수(res)에 저장하고, return값을 지정한다는 것은 dfs가 끝까지 호출된 후, 값을 상향식으로 반영하여 추려지는 조건이 있으면 그 조건대로 통과하고, 첫 출발점에 종합한 값을 저장할 수 있다는 것이다.

 

2. for문에 따라 dfs(깊이우선탐색)으로 각 경우의 수를 실행하게 된다. 문제에 주어진 시간제한 상 나머지를 구성하는 리스트를 만들어둔다.

 

1) 주어진 집합의 원소(d[i])로 문자열처럼 붙여서 순열을 구성해야 하니, d[i]마다 위치할 수 있는 자릿수 구간에 나머지를 미리 구해 저장해둔다.

 

2) 재귀함수 실행마다 rest(지금까지 누적된 나머지) + (새롭게 더해지는 집합의 원소(d[i]) * 누적된 원소의 자릿수*10**j(자릿수증가) % k 로 나머지가 누적된다. 

 

※ 주어진 리스트가 [123, 4, 5]라면 순열구성이 완료되었을 때, 12345, 41235, 12354, 51234, 45123, 54123 등 총 "다섯자리의 숫자"이며, dfs함수의 인자를 숫자의 길이(lth)를 반영하도록 하여, rest_box에서 해당하는 자릿수의 나머지를 불러올 수 있도록 구성할 수 있다. 

 

3. dp[0][0]에는 나누어떨어지는 경우의 수가 저장되어 있고, 총 경우의 수는 n!이니, factorial함수와 최대공약수를 구하는 함수를 이용해 기약분수 꼴로 출력한다.

 

 

- 코드

import sys
input = sys.stdin.readline

'''
A << B 식은 A * 2의 B제곱과 같다.
A >> B 식은 A / 2의 B제곱과 같다.
- 00001 = 1 00010 = 2 00011 = 3 00100 = 4 00101 = 5 00110 = 6 00111 = 7
- bit = (1 << n) - 1 은 n = 3일 때, 7로 이진수 111, n = 4일 때, 15로 1111
'''

n = int(input())
d = [int(input()) for _ in range(n)]
k = int(input())

dp = [[-1 for _ in range(k)] for _ in range(1 << n)]
length = [len(str(d[i])) for i in range(n)]
rest_box = [[-1 for _ in range(sum(length))] for _ in range(n)]

# d[i]의 각 자릿수마다 k로 나눈 나머지를 저장해두는 자료구조
for i in range(n):
	for j in range(sum(length)):
		rest_box[i][j] = (d[i] * (10 ** j)) % k 

def dfs(lth, bit, rest):
	if bit == (1 << n) - 1:
		if rest == 0: # 재귀함수끝(모두방문)에서 나머지 0이면 경우의 수 += 1
			return 1 
		else:
			return 0
	if dp[bit][rest] != -1:
		return dp[bit][rest]
        
# l+length[node]로 지금까지 구성된 숫자의 자릿수가 저장된다. rest는 l의 위치에서 반영한다.
# 3번째 인자 나머지 부분에서 rest_box의 (10**j)로 인해 자릿수가 맞춰지는 것을 알 수 있다.        
	for node in range(n):
		if bit & (1 << node) == 0:
			p = dfs(lth+length[node], bit|(1 << node), (rest+rest_box[node][lth])%k)
			dp[bit][rest] += p
	dp[bit][rest] += 1 # dp리스트가 -1으로 기본설정되어있으므로 += 1 해준다.
	return dp[bit][rest]

def gcd(a, b):
	while b > 0:
		a, b = b, a % b
	return a

def fac(a):
	ans = 1
	for i in range(2, a+1):
		ans *= i
	return ans

res = dfs(0, 0, 0)
F = fac(n)
if dp[0][0] == 0:
	print('0/1')
else:
	ans = gcd(F, dp[0][0])
	print(f"{res//ans}/{F//ans}")