문제 바로가기
문제:
박성원은 이 문제를 풀지 못했다. 서로 다른 정수로 이루어진 집합이 있다. 이 집합의 순열을 합치면 큰 정수 하나를 만들 수 있다. 예를 들어, {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로 출력한다.
풀이:
진짜 미친놈인가 생각이 드는 문제였다..
일단 문제는 입력값에 있는 숫자들을 붙여서 (permutations) k로 나누어지는지 구하는 간단한 문제이다.
혹시 모르니까 permutations 를 사용해 보았다. 그리고 기약분수를 만들기 위해서는 최대공약수로 나눠주면 되기 때문에
math.gcd 를 사용해서 해줬다.
import math
import sys
from itertools import permutations
n = int(input())
numbers = []
for i in range(n):
numbers.append(str(input()))
k = int(input())
down = math.factorial(n)
up = 0
for i in permutations(numbers, n):
if int("".join(i)) % k == 0:
up += 1
gcd_num = math.gcd(down, up)
print(up // gcd_num, "/", down // gcd_num, sep='')
당연 시간 초과다.
permutaions 를 사용하면 n이 15일때 15!
약 1조 3천억개가 나온다.
시간 복잡도는 O(NxN!)
- N! : 생성되는 모든 순열의 수
- n 각 순열 생성하는데 필요한 시간
백준에서 파이썬은 보통 1초 1억개를 계산한다 1조 3천이면 쉽지않다.
그럼 다른 방식으로 풀어줘야하는데 최근에 비트마스크를 사용한 동적계획법을 풀기 때문에 힌트는 그것을 사용하는것인데
나머지를 저장해서 시간을 줄여야한다는 아이디어 밖에 생각이 나지 않았다. 그래서 다른 사람들의 블로그를 참고하여 이해해보려고 한다.
1. 입력값 받고
N = int(input())
arr = [int(input()) for _ in range(N)]
K = int(input())
2. dp 설정
# i번째 비트를 사용했을때 나머지가 j인 경우의 수
dp = [[0] * K for _ in range(1 << N)]
dp[0][0] = 1 # 아무숫자 사용하지 않았을경우 나머지가 0 인 경우
dp 는 dp[사용한비트][나머지] 일때 를 나타낸다.
만약 k = 7 일때
dp[0] 에는 7개가 들어가는것이다 나머지가 0 부터 6까지 나올 수 있으니까
3. 나머지를 담을 2차원 배열
rest = []
for l in range(N):
temp = []
for j in range(K):
temp.append((j * (10 ** (len(str(arr[l]))) % K) + (arr[l] % K)) % K)
rest.append(temp)
모둘러의 연산을 사용해 l이 추가되었을때 나머지를 미리 담아주는것이다.
만약 100 에 100을 추가하면 100100 이 되는데 이것을 30으로 나눴을때 나머지를 구하는 모둘러 연산을 사용해보자
100100mod30 = {(100x1000)mod30 + 100mod30)}mod30
= {(100mod30)(1000mod30) + 100mod30}mod30
이 된다
그러면 다음 나머지를 구하는 식에서
(j * (10 ** (len(str(arr[l]))) % K) + (arr[l] % K)) % K
100mod30 이 j 가 된다 (새로운것을 붙이기 전에 수 % 30)
그리고 뒤에 붙일 수가 0자리를 길이만큼 늘려줘야하니 다음 들어올 숫자의 길이만큼 늘리고 %k 를 해준다.
+ 뒤에 오는 수 100mod30 을 넣어주고
그것들 전부의 % k를 해주면 모둘러 연산이 완료가 된다.
4. 순열
for i in range(1 << N):
for l in range(N):
# 이미 숫자가 사용됨
if i & (1 << l):
continue
# 현재 나머지 기준 새로운 나머지 계산
for j in range(K):
# 추가 했을때 새로운 나머지
next_val = rest[l][j]
dp[i | (1 << l)][next_val] += dp[i][j]
만약 n = 2 , arr =[5,6] K = 1이라고 했을때
어떻게 56 와 65가 계산되는지 의문이 될 수도 있다.
첫 번째 루프 (i = 0, 아무 숫자 사용 안 함):
- l = 0 (5 추가)
- next_val = next_vals[0][0] = 0
- dp[1 | (1 << 0)][0] += dp[0][0] 즉, dp[1][0] += 1
- l = 1 (6 추가)
- next_val = next_vals[1][0] = 0
- dp[2 | (1 << 1)][0] += dp[0][0] 즉, dp[2][0] += 1
dp = [
[1], # 아무 숫자도 사용하지 않았을 경우
[1], # 5 사용
[1], # 6 사용
[0], # 5, 6 사용
]
두 번째 루프 (i = 1, 5 사용):
- l = 0 (5 사용): 이미 사용된 숫자라서 무시.
- l = 1 (6 추가):
- next_val = next_vals[1][0] = 0
- dp[1 | (1 << 1)][0] += dp[1][0] 즉, dp[3][0] += 1
dp = [
[1], # 아무 숫자도 사용하지 않았을 경우
[1], # 5 사용
[1], # 6 사용
[1], # 5, 6 사용 (56)
]
세 번째 루프 (i = 2, 6 사용):
- l = 0 (5 추가):
- next_val = next_vals[0][0] = 0
- dp[2 | (1 << 0)][0] += dp[2][0] 즉, dp[3][0] += 1
dp = [
[1], # 아무 숫자도 사용하지 않았을 경우
[1], # 5 사용
[1], # 6 사용
[2], # 5, 6 사용 (56, 65)
]
이렇게 i와 l을 통해서 순열을 구할 수 있게 된다.
p = dp[(1 << N) - 1][0]
q = sum(dp[(1 << N) - 1])
g = math.gcd(p, q)
print(p // g, "/", q // g, sep='')
정답을 구해준다.
댓글