[BOJ 1086, C++] 박성원

https://www.acmicpc.net/problem/1086

1086번: 박성원

 

 

풀이

먼저 간단하게 생각해보면 DP 함수 인자에 문자열을 들고 다니는 것을 생각해볼 수 있지만 이렇게 하면 시간 초과가 나올겁니다.

아니면 메모이제이션 배열에 문자열을 넣을 수도 있는데, 이건 돌아갈 것 같지만 마지막에 큰 수를 나머지 연산을 이용해서 풀어야 하는 것이라 매우 귀찮은 작업이 될 수 있습니다.

 

그래서 문자열 대신 숫자로 넣어봄직을 생각해볼 수 있는데, 여기서 정수론 개념이 들어갑니다.

예제 문제로  {5221,40,1,58,9} 를 제공하였는데, 먼저 5221을 선택한다고 해봅시다. 이것을 5221 % K를 메모이제이션에 저장해두고, 이제 40을 붙인다고 생각해봅시다. 그러면 522140 = 5221 * 10^2 + 40 이라는 식을 생각할 수 있는데요.

이것은 522140 (mod K) ≡ 5221(mod K) * 100 (mod K) + 40 (mod K)가 성립합니다.

이렇게 하여 522140 % K = x라고 두고 이제 58을 붙여서 52214058을 만든다고 해봅시다.

52214058 (mod K) ≡ x (mod K) * 100 (mod K) + 58 (mod K)가 성립합니다.

이렇게 문자열, 큰 수 대신 합동식을 이용하여 K미만의 작은 수를 메모이제이션을 할 수 있게 됩니다.

 

참고로 10의 거듭제곱을 K로 나눈 나머지를 배열에 따로 저장해서 푸는 게 좋으니 위에 사용한 방법과 비슷하게 1000 (mod K) ≡ 100 (mod K) * 10 (mod K)처럼 구할 수 있습니다.

 

 

이렇게 하여 모든 가능한 개수를 구하고 유클리드 호제법을 이용하여 기약분수를 만들어주면 됩니다.

 

플레5 DP 문제중에서도 어려운 난이도에 속한 문제 같았습니다.

 

 

코드

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
using ll = long long;
 
int t, n, k;
ll dp[1 << 15][100], ten[51], mod[15];
string str[15];
 
ll gcd(ll x, ll y) {
    ll tmp;
    while (y != 0) {
        tmp = x % y;
        x = y;
        y = tmp;
    }
 
    return x;
}
 
int modular(string x) {
    int val = 0;
    for (int i = 0; i < x.size(); i++) {
        val = (val * 10 + (x[i] - '0')) % k;
    }
    return val;
}
 
ll go(int visit, int val) {
    if (visit == (1 << n) - 1) return val == 0 ? 1 : 0;
 
    ll& ret = dp[visit][val];
    if (ret != -1) return ret;
 
    ret = 0;
    for (int i = 0; i < n; i++) {
        if ((visit & (1 << i)) == 0) {
            ret += go(visit | (1 << i), (val * ten[str[i].size()] + mod[i]) % k);
        }
    }
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    memset(dp, -1, sizeof(dp));
 
    cin >> n;
    for (int i = 0; i < n; i++) cin >> str[i];
    cin >> k;
 
    for (int i = 0; i < n; i++) mod[i] = modular(str[i]);
 
    ten[0] = 1;
    for (int i = 1; i < 51; i++) {
        ten[i] = (ten[i - 1] * 10) % k;
    }
 
 
 
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += go(1 << i, mod[i]);
    }
 
    ll fac = 1;
    for (int i = 1; i <= n; i++) {
        fac *= i;
    }
 
    if (ans == 0) cout << "0/1";
    else if (ans == fac) cout << "1/1";
    else cout << ans / gcd(fac, ans) << "/" << fac / gcd(fac, ans);
 
    cout << endl;
}