[백준] 1086 박성원

문제 주소 : www.acmicpc.net/problem/1086

1086번: 박성원

문제 확인

 

bit dp 문제입니다. 입력받는 숫자의 개수가 15개 이므로 bit 형으로 표현할 수 있으며 나머지 값인 k 또한 100보다 작은 수 이므로 dp[1<<15][101]로 나타낼 수 있습니다.

bit dp : justicehui.github.io/hard-algorithm/2019/01/18/bitDP/

Bit DP

 

풀이

 

입력되는 수의 크기가 50자리수를 넘으므로 k로 나눈 나머지를 배열로 저장합니다. 모듈러 연산자 또한 다른 연산자처럼 다음과 같은 성질을 가집니다.

어떠한 수 a = x + y 가 있을 때 a % k = x % k + y % k 를 만족합니다.

이러한 성질을 이용해 나머지만 배열에 저장해둔 후 이어붙혀 계산할 수 있습니다.

 

dp 점화식을 세워보면 n개의 수가 있다고 하면 dp[0000 ... 001][0] 이 가지는 의미는 1번째 숫자를 사용하면서 그 수를 k로 나눈 나머지가 0이라는 의미를 가집니다. 각 비트 필드를 채우면서 나머지가 특정 값이 되는 경우의 수를 더해갑니다.

따라서 점화식은 dp[i | (1 << t)][(j*octal[size[t]] + ary[t]) % k] +=dp[i][j] 가 됩니다.

i | (1 << t)의 의미는 다른 수를 이어붙이고, (j*octal[size[t]] + ary[t]) % k 의 의미는 이어 붙인 수를 k로 나눈 나머지를 의미하며 현재까지 경우의 수를 넘겨줍니다.

 

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
 
long long gcd(long long a, long long b) {
    long long r;
    while (b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}
int main() {
    int n, k;
    char tmp[15][51];
    long long dp[1 << 15][101] = { 0 };
    int ary[15] = { 0 }, size[15], octal[51];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", tmp[i]);
        size[i] = strlen(tmp[i]);
    }
    scanf("%d", &k);
    octal[0] = 1;
    for (int i = 1; i <= 50; i++)
        octal[i] = (octal[i - 1] * 10) % k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < size[i]; j++) {
            ary[i] = ((tmp[i][j] - '0') + ary[i] * 10) % k;
        }
    }
    dp[0][0] = 1;
    for (int i = 0; i < (1 << n); i++) 
        for(int j=0;j<k;j++)
            for (int t = 0; t < n; t++) 
                if ((i&(1 << t)) == 0) 
                    dp[i | (1 << t)][(j*octal[size[t]] + ary[t]) % k] += dp[i][j];
                
 
    long long p = dp[(1<<n)-1][0], q = 1;
    for (long long i = 2; i <= n; i++)q *= i;
    long long t = gcd(p, q);
    p /= t;
    q /= t;
    printf("%lld/%lld", p, q);
}