Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

33. 동적 계획법3

비트마스크를 배우고, 동적 계획법에 적용해 봅시다. 그 후에는 선형이 아니라 원형으로 구성된 문제를 다룹니다.

Java / Python

4. 박성원

1086번

박성원이 풀지 못한 문제

이번 문제는 N이 최대 15개 주어질 때, 이 수를 모두 사용한 순열을 순서대로 이어붙인 숫자 중 k(K는 100보다 작거나 같은 자연수)로 나눠떨어지는 것의 개수를 이용해서 확률을 구하는 문제이다. 정답은 기약분수 형태로 출력해야 한다.

• Java

import java.io.*;
import java.util.*;

public class Main {
	static int N, K;
	static char[][] set;
	static long p, q;

	static long[] fibo;
	static int[][] dpMod;
	static long[][] dp;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		set = new char[N][];
		for (int i = 0; i < N; i++) {
			set[i] = br.readLine().toCharArray();
		}
		K = Integer.parseInt(br.readLine());

		fibo = new long[N + 1];
		fibo[1] = 1L;
		for (int i = 2; i <= N; i++) {
			fibo[i] = (long) i * fibo[i - 1];
		}

		dp = new long[K][1 << N];
		dpMod = new int[K][N];
		for (int i = 0; i < K; i++) {
			Arrays.fill(dp[i], -1);
			Arrays.fill(dpMod[i], -1);
		}

		p = memoization(0, 0, 0);
		q = fibo[N];
		if (p == 0) {
			q = 1;
		} else {
			long gcd = GCD(p, q);
			p /= gcd;
			q /= gcd;
		}

		bw.write(p + "/" + q + "\n");

		bw.flush();
		bw.close();
		br.close();
	}

	public static long GCD(long a, long b) {
		if (a > b) {
			long tmp = a;
			a = b;
			b = tmp;
		}

		while (a % b != 0) {
			long tmp = a % b;
			a = b;
			b = tmp;
		}
		return b;
	}

	public static int getMod(int mod, int n) {
		if (dpMod[mod][n] != -1) {
			return dpMod[mod][n];
		}

		int now = mod;
		for (int j = 0; j < set[n].length; j++) {
			now = now * 10;
			now = (now + set[n][j] - '0') % K;
		}

		return dpMod[mod][n] = now;
	}

	public static long memoization(int mod, int cnt, int flag) {
		if (dp[mod][flag] != -1) {
			return dp[mod][flag];
		}

		if (cnt == N) {
			return dp[mod][flag] = mod == 0 ? 1L : 0;
		}

		long sum = 0;
		for (int i = 0; i < N; i++) {
			if ((flag & (1 << i)) != (1 << i))
				sum += memoization(getMod(mod, i), cnt + 1, flag | (1 << i));
		}

		return dp[mod][flag] = sum;
	}
}

• Python

import sys
import math
input = sys.stdin.readline

n = int(input())
s = [int(input()) for _ in range(n)]
k = int(input())
r = [[(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 b in range(1<<n):
    for i in range(n):
        if b&(1<<i): continue
        for j in range(k):
            dp[b|(1<<i)][r[i][j]]+=dp[b][j]
p = dp[(1<<n)-1][0]
q = sum(dp[(1<<n)-1])
g = math.gcd(p,q)
print("%d/%d"%(p//g,q//g))