1086 박성원 (비트,DP)

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

1.접근

방문했던곳들의 상태를 표기하기 쉽도록 비트마스크를 사용하고 n이 15일때 15!로 숫자가 크므로

DP를 사용해줘야 한다.

2.풀이

분모를 N!,분자를 k로 나눠떨어지는 경우의 수로 두는 문제이다.그래서 나는 DP배열을

DP[방문한곳][현재 나머지]로 만들고 DP[방문한곳][현재 나머지]=방문할 수 있는 곳들에서의 경우의 수 합 으로 점화식을 만들었다.그렇게 DFS를 사용하여 방문했던 곳이 나오면 그대로 값을 리턴하고 만약 모든 곳을 방문하고 나머지가 0일 때는 1을 리턴해주는 함수DFS를 만들었다.

나머지는 (이번에 추가하는 숫자*10**현재수의 길이) 현재 나머지를 더하고 k로 나눠주면서 저장하면 된다.

DP를 0으로 초기화 해두면 이미 0으로 메모제이션 된곳도 착각할까봐 -1로 초기화 하였다.

3.코드

	import sys
	from math import gcd,factorial
	input=sys.stdin.readline
	def dfs(L,visit,rest):
	if visit==(1<<n)-1:
	if rest==0:
	return 1
	else:
	return 0
	if dp[visit][rest]!=-1:
	return dp[visit][rest]
	for i in range(n):
	if visit&(1<<i)==0:
	dp[visit][rest]+=dfs(L+long[i],visit|(1<<i),(rest+rm[i][L])%k)
	dp[visit][rest]+=1
	return dp[visit][rest]
	n=int(input())
	stack=[]
	for _ in range(n):
	stack.append(int(input()))
	long=[]
	for i in stack:
	long.append(len(str(i)))
	k=int(input())
	dp=[[-1]*k for _ in range(1<<n)]
	rm = [[-1]*(sum(long)) for _ in range(n)]
	for i in range(n):
	for j in range(sum(long)):
	rm[i][j] = (stack[i]*10**j)%k
	temp=dfs(0,0,0)
	F=factorial(n)
	if temp==0:
	print('0/1')
	else:
	v=gcd(F,dp[0][0])
	print('{}/{}'.format(temp//v,F//v))

view raw 1086 박성원.py hosted with ❤ by GitHub

4.배운점

• gcd와 팩토리얼을 구현했었는데 math모듈에 다 있었다.
• 나머지에 대한 개념이 확실하지 않다
• rm배열을 만들지 않아놓고 계속 계산을 했었는데 그 곳에서 시간초과가 계속 났다. 수가 너무 큰 계산이라서 시간을 오래 잡아 먹는 것 같다. 다음에는 수가 큰 계산이 반복되면 배열로 선언해 놔야겠다.