백준[1086] 박성원

문제 설명

풀이

dp와 비트마스크를 이용하여 풀 수 있다.

dp[나머지][현재 상태] = 현재 상태일 때 나머지

입력받는 수가 최대 50자리로 매우 큰 숫자이기 때문에 string으로 입력을 받고 큰 수의 나머지 값을 구해 저장해둬야 한다.

(새로운 나머지) = (새로운 수) % k = ((이전 나머지) * 10 ^ (이전 수 길이) + (추가될 수)) % k = (이전 나머지) * 10 ^ (이전 수 길이) % k + (추가 될 수) % k이기 때문에 10^n % k의 값을 미리 구해놓는다. 이 부분은 아이디어가 생각나지 않아서 여기를 참고했다.

값의 출력은 기약 분수로 해야 하기 때문에 p, q의 최대 공약수를 구하여 p, q에 각각 나눴다.

나는 처음에 dp정의를 dp[현재 노드][나머지][현재 상태]로 정의하여 메모리 초과가 났다. 메모리 초과는 처음 경험했기 때문에 dp를 정의할 때 메모리를 계산해보는 습관을 들여야겠다.

코드

#include <iostream>
#include <string>
#include <cstring>
#include <numeric>

using namespace std;
using ll = long long;

ll arr[16];
string input[16];
ll dp[102][1 << 15], pw[55], len[16];
ll K, N;

ll fac(ll n) {
    ll ans = n;
    while (--n) {
        ans *= n;
    }
    return ans;
}

ll dpf(ll mod, ll state) {
    ll &ret = dp[mod][state];
    if (~ret) return ret;
    if (state + 1 == 1 << N) {
        if (mod) return 0;
        else return 1;
    }
    ret = 0;
    for (int i = 0; i < N; i++) {
        if (!(state & (1 << i))) {
            ll num = mod * pw[len[i]] + arr[i];
            ret += dpf(num % K, state | (1 << i));
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> input[i];
    }
    cin >> K;
    for (int i = 0; i < N; i++) {
        len[i] = input[i].size();
        ll t = 0;
        for (auto c : input[i]) {
            t *= 10;
            t %= K;
            t += c - '0';
            t %= K;
        }
        arr[i] = t;
    }

    pw[0] = 1 % K;
    for (int i = 1; i < 55; i++) {
        pw[i] = (pw[i - 1] * 10) % K;
    }
    memset(dp, -1, sizeof(dp));
    ll p = dpf(0, 0);
    if (p == 0) {
        cout << "0/1";
        return 0;
    }
    ll q = fac(N);
    ll divider = gcd(p, q);
    cout << p / divider << "/" << q / divider;
}

문제 링크: https://www.acmicpc.net/problem/1086