[백준/Python]1086: 박성원

문제

https://www.acmicpc.net/problem/1086
백준 단계별로 풀어보기 - 동적 계획법 3

---

풀이

비트마스킹 + DP 를 고려하지 않고 풀었을땐 쉬웠는데, 이 둘을 적용하려니 어려웠던 문제다...
생각해보면 당연하다. 단순히 permutations 모듈을 사용해서 풀면 메모리&시간이 엄청나게 소요된다.
그래서 시도했는데...
DP도 어려운데 비트마스킹까지 적용하려니 힘들었다... 결국 다른 풀이를 참고해서 공부했다^^;;
 
다른 풀이들을 찾아보니 단순히 저 둘을 접목시킨다고 해결되는 문제가 아닌듯했다. (시간초과)
더 효율적인 방법을 생각해내야하는 문제다.
 
 

어떠한 수를 K로 나누었을때 나머지값의 범위는 0 ~ K-1이다.
이걸 이용해서 주어진 집합의 각 숫자 S[i]에 대해 가능한 나머지값들을 저장한다.

remain = [[(j * 10 ** len(str(S[i])) + S[i]) % K for j in range(K)] for i in range(N)]

 

하나씩 뜯어보면,
for i in range(N): 집합 S의 각 원소에 대한 인덱스 i
for j in range(K): i를 추가하기 전의 나머지값 j
즉, remain[i][j]는 "현재 나머지가 j인 상황에서, S[i]를 추가했을의 나머지" 를 나타낸다.

(j * 10 ** len(str(S[i])) + S[i]) % K를 뜯어보면 아래와 같다.
j * 10 ** len(str(S[i])): 기존 나머지 j를 S[i]의 길이만큼 왼쪽으로 밀어냄
+ S[i]: 그 후 S[i]를 더해줌
% K: 위의 값을 K로 나눈 나머지

 

만약 기존 나머지가 3인 상황에서 S[1] = 2를 추가하고 싶다면 remain[1][3]값을 가져오면 된다.

 
그리고 dp는 아래와 같이 초기화한다.

dp = [[0] * K for _ in range(1 << N)]
dp[0][0] = 1

숫자의 조합을 비트마스킹으로 나타냈을때의 값을 i라고 했을때, 그 조합의 나머지가 j인셈이다.
dp[3(011)][2]: 첫번째와 두번째 원소를 조합했을때, 나머지가 2인경우.

 
 

전체 코드는 아래와 같다.

from sys import stdin
import math


input = stdin.readline

N = int(input())
S = [int(input()) for _ in range(N)]
K = int(input())

remain = [[(j * 10 ** len(str(S[i])) + S[i]) % K for j in range(K)] for i in range(N)]

dp = [[0] * K for _ in range(1 << N)]
dp[0][0] = 1

for mask in range(1 << N):
    for i in range(N):
        if mask & (1 << i):  # 🚨 if not으로 체크할때보다 더 빠름.
            continue
        for j in range(K):
            dp[mask | (1 << i)][remain[i][j]] += dp[mask][j]

correct = dp[(1 << N) - 1][0]
total = sum(dp[(1 << N) - 1])
m = math.gcd(correct, total)
print(f"{correct // m}/{total // m}")

 

mask는 가능한 조합을 나타낸다. (만약 N이 3이라면 000 ~ 111)
i는 추가할 인덱스를 의미하며, 만약 i번째 인덱스가 이미 mask조합에 포함된 상태라면 패스.
j는 나머지값으로 올 수 있는 범위다.

 

[mask | (1 << i)]: i번째 인덱스를 추가한 뒤의 조합
[remain[i][j]]: 기존 나머지값이 j일때 i번째 인덱스를 추가한 후 나머지값
=> dp[mask | (1 << i)][remain[i][j]]: 선택한 조합에 i인덱스를 추가했을때, 나머지가 remain[i][j]인 경우의 수.

 

이 경우의 수에 "i인덱스를 추가하기 전 경우의 수"를 더해준다.

dp[mask][j]: 선택한 조합이 mask일때 나머지가 j인 경우의 수

 
이렇게 반복문을 진행하며 각 조합에 대해 가능한 모든 나머지값을 계산하고,
최종적으로 모든 조합을 사용했을때 나머지가 0인 경우, 모든 조합을 사용했을때의 경우의 수를 구할 수 있다.

마지막으로 math모듈의 gcd()함수를 사용해 최대공약수를 구하고, 각 값을 최대공약수로 나눠 출력한다.

 
 

+ 그리고 if not mask $ (1 << i):로 사용했을때보다 위처럼 작성했을때가 더 빨랐다.
if not처럼 사용할 경우 "해당 조건문을 만족하지 않을 경우"도 체크하기 때문에, 모든 경우에 대해 추가적인 작업이 진행될 수도 있다고 한다.
반면 continue는 조건이 참일 경우 바로 반복문을 빠져나오므로 위 문제처럼 반복이 많아질 때 효과적이라고 한다.
... ~그렇다고 한다. GPT를 100% 신뢰할 순 없으니 가능성으로만 남겨두자.