백준 1086번: 박성원 (Python, PyPy3)

접근

다른 개인적인 코딩공부를 하다가 오랜만에 알고리즘 문제를 다시 풀려고 하니 역시 머리가 굳어서 잘 생각이 나지도 않고, 심지어 익숙하지 않은 비트마스크를 이용한 DP 문제여서 푸는데 시간이 더 많이 걸렸다.

비트마스크 DP 문제 : 2021.05.10 - [코딩/백준 (Python)] - 백준 1311번: 할 일 정하기 1 (Python, PyPy3)

백준 1311번: 할 일 정하기 1 (Python, PyPy3)

아직 개념이 익숙치 않아 좀 더 공부한 후 다시 설명 예정

코드

import sys
from math import gcd, factorial

n = int(sys.stdin.readline())
stack = []
for _ in range(n):
    stack.append(int(sys.stdin.readline()))
long = []
for i in stack:
    long.append(len(str(i)))
k = int(sys.stdin.readline())
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


def dfs(L, visited, rest):
    if visited == (1 << n) - 1:
        if rest == 0:
            return 1
        else:
            return 0
    if dp[visited][rest] != -1:
        return dp[visited][rest]
    for i in range(n):
        if visited & (1 << i) == 0:
            dp[visited][rest] += dfs(L + long[i], visited | (1 << i), (rest + rm[i][L]) % k)
    dp[visited][rest] += 1
    return dp[visited][rest]


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))

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!