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.코드

4.배운점

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