🎲문제

---

주소: 백준 1086

박성원은 이 문제를 풀지 못했다.

서로 다른 정수로 이루어진 집합이 있다. 이 집합의 순열을 합치면 큰 정수 하나를 만들 수 있다. 예를 들어, {5221,40,1,58,9}로 5221401589를 만들 수 있다. 합친수가 정수 K로 나누어 떨어지는 순열을 구하는 프로그램을 작성하시오.

하지만, 박성원은 이 문제를 풀지 못했다.

따라서 박성원은 그냥 랜덤하게 순열 하나를 정답이라고 출력하려고 한다. 이 문제에는 정답이 여러 개 있을 수도 있고, 박성원이 우연히 문제의 정답을 맞출 수도 있다.

박성원이 우연히 정답을 맞출 확률을 분수로 출력하는 프로그램을 작성하시오.

⌨ 입력

---

첫째 줄에 집합의 수의 개수 N이 주어진다. N은 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 집합에 포함된 수가 주어진다. 각 수의 길이는 길어야 50인 자연수이다. 마지막 줄에는 K가 주어진다. K는 100보다 작거나 같은 자연수이다.

✅ 풀이

---

풀이방법

비트마스킹과 메모이제이션을 사용하고, 큰 수 연산을 위해 모듈러 연산, 최소공배수를 구하기위한 유클리드 호제법을 사용한다. 익숙하지 않은 비트마스킹과 여러 개념들이 섞여 있어 풀기 쉽지 않았다. 비트마스킹을 통해 숫자 나열 순회의 정보를 저장하고, 재귀를 통해 숫자 나열 순서를 반복한다. 해당 순서의 나머지를 나타내는 배열, 해당 순서와 나머지, 나누어 떨어지는 개수를 저장한 배열, 총 2개의 dp배열을 사용하여 문제를 해결한다.

1. N을 입력받고 편한 모듈러 연산을 위해 각 숫자를 char 2차원 배열을 통해 저장한다.
2. 각 집합의 순서를 정하는 방법의 수는 N! 이다. 분모로 사용하기 위한 해당 정보는 memo배열에 dp로 저장한다.
3. K를 입력받고 분모가 될 q에 memo배열의 숫자를 넣는다. 순서와 나머지, 그 순서로 진행했을 때 나누어 떨어지는 개수를 저장한 dp2차원 배열과, 특정 순서의 숫자를 K로 나누었을때의 나머지를 저장할 dpMod 배열을 선언한다.
4. 선언한 위 두 배열을 -1로 초기화한다.

        N = Integer.parseInt(br.readLine());

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

        memo[1] = 1;

        for(int i = 2; i <= N; i++)
            memo[i] = memo[i-1] * i;

        K = Integer.parseInt(br.readLine());

        q = memo[N];
        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);
        }

5. 본격적으로 딱 떨어질 개수를 구할 dp함수를 분자가 될 p함수에 담는다.

 p = memoization(0, 0, 0);
	//메인함수

6. p에 적용될 dp함수를 선언한다. 이미 dp배열이 다른 수로 한 번 더 초기화 되었다면 초기화 된 값을 반환한다. 전체 숫자를 한바퀴 돌았을 때가 종료조건으로, cnt 가 N에 되었을 때 나누어 떨어진다면 1을 dp배열에 저장하고 반환하고, 아니라면 0을 저장하고 반환한다.
7. 반복문과 비트 and or 연산을 통해 현재 순서의 다음 순서들을 결정하고 해당 값을 sum에 더한다.
8. 현재 순서의 하위순서들의 나누어 떨어지는 개수를 반복문을 통해 sum에 모두 더했다면 해당 정보를 dp에 기록하고 상위에 반환한다.

    public static long memoization(int flag,int mod, int cnt){
        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(flag | (1 << i), getMod(mod, i), cnt + 1 );
        }

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

9. 해당 함수는 모듈러연산을 통해 숫자 10 순서 / k 의값을 구하고 해당 값을 dpMod값에 저장하는 함수이다. 해당 연산도 중복되는 연산이기 때문에 메모이제이션을 통해 중복되는 연산을 줄인다.

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

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

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

10. 마지막으로 분자가 0이라면 0/1로 표현해야 하므로 해당 경우를 처리하고 나머지의 경우는 기약분수로 나타내기 위해 유클리드 호제법을 사용하여 최소 공배수를 구한다.
11. 최소 공배수를 각각의 값에 나누어 기약분수로 나타낸 값을 출력한다.

        if(p == 0){
            q = 1;
        }else{
            long gcd = getGCD(p,q);
            p /= gcd;
            q /= gcd;
        }

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

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

    }

12. 아래 함수는 유클리드호제법과 메모이제이션을 통해 최소 공배수를 구하는 함수이다.

    public static long getGCD(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;
    }

💯 전체 코드

---

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

public class Main{

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int N, K;
    static char[][] set;
    static long[] memo = new long[16];
    static long[][] dp;
    static int[][] dpMod;
    static long p, q;

    public static void main(String[] args) throws Exception{
        N = Integer.parseInt(br.readLine());

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

        memo[1] = 1;

        for(int i = 2; i <= N; i++)
            memo[i] = memo[i-1] * i;

        K = Integer.parseInt(br.readLine());

        q = memo[N];
        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);
        if(p == 0){
            q = 1;
        }else{
            long gcd = getGCD(p,q);
            p /= gcd;
            q /= gcd;
        }

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

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

    }

    public static long getGCD(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 long memoization(int flag,int mod, int cnt){
        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(flag | (1 << i), getMod(mod, i), cnt + 1 );
        }

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

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

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

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