박성원

백준 1086번: 박성원

아이디어

주어진 순자를 하나씩 골라 뒤로 붙이면서 점점 큰 숫자를 만든다. 이 때 숫자가 커질 수 있으므로 나머지만 취한다. 어차피 나누어 떨어지는지 확인만 하면 됨.

a뒤에 b를 붙이면 (a×10^b.length)+b이고 나머지를 계속 계산해야 하므로 a%K, 10^b.length%K, b%K를 알면 된다.
10^n%K와, a%K, b%K를 전부 미리 계산해놓아야 TLE를 피할 수 있다.

이렇게 숫자를 하나씩 붙이다 모든 숫자를 사용한 경우, 현재 나머지가 얼마인지 확인하고, 0이면 성립하므로 1을 반환한다.

현재 어떤 숫자를 사용했는지와 현재 나머지가 몇인지를 기준으로 메모이제이션 한다.

10, 1, 101, 200 이렇게 4개의 숫자가 있다고 하자.
10-1-101 순서로 붙이나 101-10-1 순서로 붙이나 나머지가 같기 때문에 숫자를 사용한 순서를 기록할 필요는 없다

코드

#include <bits/stdc++.h>

using namespace std;

#define int long long

int N, K;
int cache[1<<15][100], arr[15], pre[51];
vector<string> v;

int solve(int check, int mod) {
    if (check == (1<<N)-1) {
        return mod ? 0 : 1;
    }

    int& ret = cache[check][mod];
    if (ret != -1) return ret;

    ret = 0;
    for (int i = 0; i < N; i++) {
        if (check & (1<<i)) continue;
        int m = mod*pre[v[i].length()]%K;
        ret += solve(check|(1<<i), (m+arr[i])%K);
    }
    
    return ret;                   
}

int gcd(int a, int b) {
    if (!b) return a;
    return gcd(b, a%b);
}

int fact(int n) {
    if (n == 1) return 1;
    return n*fact(n-1);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    v.resize(N);
    
    for (int i = 0; i < N; i++) {
        cin >> v[i];
    }
    cin >> K;

    // 10^n % K 계산 (최대 길이 50)
    pre[0] = 1;
    for (int i = 1; i < 51; i++) {
        pre[i] = pre[i-1]*10%K;
    }

    // 입력받은 긴 숫자 % K 계산
    for (int i = 0; i < N; i++) {
        int m = 0;
        for (char& c : v[i]) {
            m = m*10 + (c-'0');
            m %= K;
        }
        arr[i] = m;
    }

    memset(cache, -1, sizeof(cache));
    
    int a = solve(0, 0);
    int b = fact(N);
    int g = gcd(a, b);
    cout << a/g << '/' << b/g;

    return 0;
}

여담

왜 900ms나 걸렸을까? 어디가 문제일까?..
아 그리고 long long 써야함.