BOJ 1086 박성원

문제출처

참고1
참고2

정말정말정말 힘들었던 문제ㅎㅎㅎ사실 아직 완전히 이해를 완료하지 못했고 위 참고 사이트들의 도움 없이는 다시 풀지도 못 할 것 같지만 컨닝으로라도 문제를 푼 과정을 정리하는 것은 의미가 있을 것 같아 여기에 정리한다.
괜히 주저리주저리...문제로 들어가자.

아이디어

1. dp 배열

문제 해결을 위한 알고리즘이 DP와 비트마스킹이라는 것만 알고 시작했는데, dp 배열에 무엇을 저장해야 할지 전혀 감을 잡지 못했다.
찾아보니 아래와 같이 저장하면 된다고 한다.

dp[i][j] : i(비트)번 숫자들을 사용했을 때 나머지가 j(정수)인 경우의 수 (j ≤ K)

ex) 순열(arr)이 $\{25, 100, 49, 333\}$이고 $K$가 $5$일 때, dp[1010][3] 를 계산해보자.

• $1010_{(2)}$는 비트마스킹에서 2번과 4번을 의미한다.
• 2번 숫자는 $100$ 4번 숫자는 $333$이므로 가능한 경우는 $[100333, 333100]$ 두 가지이다.
• 이를 $5$로 나눈 나머지는 $[3, 0]$이고 이 중 $3$은 1개 이므로 dp[1010][3]=1이다.

위에 따르면 결국 구해야 하는 값은 $\text{dp}\left[2^{n}-1\right]\left[0\right]$의 값과 $\sum_{i=0}^{K}\text{dp}\left[2^{n}-1\right]\left[i\right]$이다.

2. 점화식

i 비트들로 만든 숫자 뒤에 l번째 숫자를 뒤에 더한다고 해보자.
즉 위의 예시에서 2번째와 4번째(1010) 숫자를 가지고 만든 $[100333, 333100]$의 뒤에 3번째 숫자인 $49$를 더하는 것이다. 그 결과는 $[10033349, 33310049]$이다.

새로 만들어진 수($[10033349, 33310049]$)로 업데이트할 수 있는 것을 찾는 것이 이 문제의 핵심이다.
다시 말해 dp[i][j]의 값을 통해 dp[i | 1 << l][next]의 값을 업데이트할 것인데 이때 next의 값이 무엇인지, 어떻게 업데이트되는 것인지를 파악해야 한다.

우선 next의 값이 무엇인지 알아보자. 다음 식을 통해 알 수 있다.

$K$의 값, l번째 수는 문제에서 주어지므로 $i, j$ 값만 안다면 next의 값을 알 수 있다.

이제 next의 값은 알았는데, 대체 dp[i|1<<l][next]의 값은 어떻게 안단 말인가? 정답은 더해주는 것이다. (이 부분이 내게 매우 어려운 부분이었다!)

dp[i|1<<l][next]의 의미를 다시 생각해보자.

• i번 숫자들을 사용해서 만든 숫자들에 l번 숫자를 뒤에 붙였을 때 만들어지는 새로운 숫자들이 $K$로 나눈 나머지가 next인 경우의 수를 의미한다.
• next는 i와 j와 l에 의해 결정된다.
• 그렇다면 모든 가능한 [i, j, l]의 조합에 대해 나오는 경우의 수를 다 더하는 것이 dp[i|1<<l][next]의 값이 된다.

미리 코드로 표현하자면 다음과 같다.

for i in range(1 << N):
    for l in range(N):
        if i & (1 << l):
            continue
        for j in range(K):
            # next_val = (j * (10^(len(arr[l])) % K) + (arr[l] % K)) % K
            next_val = next_vals[l][j]  # next_vals 배열은 뒤의 코드에서 확인 가능
            dp[i | (1 << l)][next_val] += dp[i][j]

3. 초기값

점화식도 세웠으니 이제 dp 배열의 초기값만 정해주면 된다.
dp[0][0]의 값의 의미를 생각해보면 아무 숫자도 고르지 않은 수를 $K$로 나눈 나머지가 $0$인 경우의 수이다.
'아무 숫자도 고르지 않은 수'를 $0$이라고 보면 dp[0][0]=1임을 생각해낼 수 있다.

아이디어 마무리

dp 배열의 의미, 점화식, 초기값 모두 정해졌으니 이제 로직만 만들면 된다.

코드

1. 초기화

dp 배열을 만들어주자. 행은 비트를 표현하므로 $2^N$개 필요하고 열은 $K$로 나눈 나머지를 의미하므로 $K$개 필요하다.
그리고 초기값을 $1$로 설정한다.

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

2. next 배열

앞서 본 것처럼 next의 값은 다음 수식으로 표현할 수 있다.

변수로 따지만 j과 l밖에 없으므로 사실상 i를 고려하지 않고 값을 계산할 수 있다.
프로그래밍에서 이는 비트의 반복문인 i의 반복문과 관계가 없다는 의미이므로 next 값을 미리 계산해놓은 배열을 만들어놓고 i의 반복문에서 해당 값을 참조하는 형태로 만드는 것이 바람직하다.

next_vals = []
for l in range(N):
    temp = []
    for j in range(K):
        temp.append((j * (10 ** (len(str(arr[l]))) % K) + (arr[l] % K)) % K)
    next_vals.append(temp)

3. 반복문

모든 가능한 [i, j, l]의 조합을 따져야 하므로 삼중 for문을 사용한다. 이때 비트를 의미하는 i의 반복문 뒤에 순열의 숫자를 의미하는 l의 반복문을 넣어 경우의 수를 최소화 한다.

for i in range(1 << N):
    for l in range(N):
        if i & (1 << l):
            continue
        for j in range(K):
            next_val = next_vals[l][j]
            dp[i | (1 << l)][next_val] += dp[i][j]

4. 분수로 나타내기

dp 배열의 업데이트가 끝났으면 기약분수로 나타내면 되는데, 여기에는 최대공약수를 구하는 로직이 필요하다. 파이썬이라면 math 모듈로 쉽게 구할 수 있지만 백준의 또다른 문제에서 풀어본 적 있는 방법을 사용했다.

def gcd(a: int, b: int):
    if b == 0:
        return a
    return gcd(b, a % b)

분모는 dp배열의 마지막 행의 값의 합, 분자는 마지막 행 $0$번째 열의 값이다. 다음과 같이 작성하면 된다.

p = dp[(1 << N) - 1][0]
q = sum(dp[(1 << N) - 1])
g = gcd(p, q)
print(f"{p // g}/{q // g}")

정답 코드

import sys


def gcd(a: int, b: int):
    if b == 0:
        return a
    return gcd(b, a % b)


def main():
    input = sys.stdin.readline
    N = int(input())
    arr = [int(input()) for _ in range(N)]
    K = int(input())
    dp = [[0] * K for _ in range(1 << N)]
    dp[0][0] = 1

    next_vals = []
    for l in range(N):
        temp = []
        for j in range(K):
            temp.append((j * (10 ** (len(str(arr[l]))) % K) + (arr[l] % K)) % K)
        next_vals.append(temp)

    for i in range(1 << N):
        for l in range(N):
            if i & (1 << l):
                continue
            for j in range(K):
                next_val = next_vals[l][j]
                dp[i | (1 << l)][next_val] += dp[i][j]
    p = dp[(1 << N) - 1][0]
    q = sum(dp[(1 << N) - 1])
    g = gcd(p, q)
    print(f"{p // g}/{q // g}")


if __name__ == '__main__':
    main()

마무리

너무 빡세다...........비트 마스킹은 아직도 어떤 걸 배열의 인덱스로 사용해야 하는지 헷갈린다........공부가 많이 필요함....^^