boj1086 박성원

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

1086번: 박성원

 

boj 2098 외판원 순회와 푸는 방식이 조금 비슷하다. 

하지만 그렇다고 방심하면 절대 안된다....

 

 

- 처음에 막혔던 것은

 

23489178492738953489278913278943 % k 를 구하고(a)

그 다음  a 와 38941023890582943829048130248029 를 합친 수 % k 를 구하고(b)....

 

를 좀 더 빠르게 구할 방법이 없을까 이다.

 

답은 na[100][1<<n]를 만들어 행에는 나머지 a , 열은 arr[i] 를 기준으로 메모이제이션을 해주면 된다.

 

 

 

그래서 일단 만들어 봤다.

#include <iostream>
#include <algorithm>
#include <string>
#define pii pair<int, int>
#define ll long long int
using namespace std;
 
 
string arr[15];
int get_na[100][15]; // i과 arr[i]를 합친 후의 MOD;
int n, na;
ll d[15][1 << 15];
 
 
ll go(int cur, int cur_mod, int visit)
{
    if (visit == (1 << n) - 1)
    {
        if (cur_mod == 0)
            return 1;
        else
            return 0;
    }
 
    if (d[cur][visit] != -1)
        return d[cur][visit];
    else
        d[cur][visit] = 0;
 
    for (int i = 0; i < n; i++)
    {
        if ((visit & (1 << i)) != 0)
            continue;
 
        d[cur][visit] += go(i, get_na[cur_mod][i], visit + (1 << i));
    }
 
    return d[cur][visit];
 
}
 
ll get_GCD(ll a, ll b)
{
    if (b == 0)
        return a;
    else
        get_GCD(b, a % b);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    cin >> na;
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < (1 << n); j++)
            d[i][j] = -1;
    }
    for (int i = 0; i < na; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int init = i;
 
            for (int k = 0; k < arr[j].size(); k++)
            {
                init = (init * 10 + (arr[j][k] - '0')) % na;
            }
            get_na[i][j] = init;
        }        
    }
 
    ll ans = 0;
    
    for (int i = 0; i < n; i++)
        ans += go(i, get_na[0][i], 1 << i);
 
//    cout << ans << '\n';
 
    ll can = 1;
    for (int i = 2; i <= n; i++)
        can = can * i;
 
    if (can == ans)
        cout << "1/1";
    else if (ans == 0)
        cout << "0/1";
    else
    {
        ll GCD = get_GCD(can, ans);
        cout << ans/GCD << '/' << can/GCD;
    }    
 
}

 

하지만 런타임 에러가 나를 오랫동안 괴롭혔다.

 

한참을 찾은 결과 get_GCD의 함수가 런타임 에러를 뿜었던 것이였다. 아니 왜 저렇게 쓰면 안되는거지????? 

나중에 찾아봐야겠다.

 

ll getGCD(ll a, ll b)
{
    if (b == 0)
        return a;
    else
        getGCD(b, a % b);
} // 안됨
 
 
 
 
ll getGCD(ll a, ll b)
{
    if (a % b == 0)
        return b;
    else
        return getGCD(b, a % b);
} // 됨

하지만 뭔가 맞은거 같지만 틀렸다. 그래서 d[][] 부분을 다르게 고쳤다.

개인적인 추측으로는 탑다운 방식을 쓸때 go()함수를 여러번 써서 그런것 같다.

 

 

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define pii pair<int, int>
#define ll long long int
using namespace std;
 
string arr[15];
int n, k;
 
ll d[100][1 << 15];
ll na[100][15];
 
 
ll go(int cur_na, int visit)
{
    
    if (visit == (1 << n) - 1)
    {
        if (cur_na == 0)
            return 1;
        else
            return 0;
    }
 
    if (d[cur_na][visit] != -1)
        return d[cur_na][visit];
 
    d[cur_na][visit] = 0;
 
 
    for (int i = 0; i < n; i++)
    {
        if ((visit & (1 << i)) != 0)
            continue;
 
        d[cur_na][visit] += go(na[cur_na][i] ,visit | (1 << i));
    }
 
    return d[cur_na][visit];
}
 
 
 
 
ll getGCD(ll a, ll b)
{
    if (a % b == 0)
        return b;
    else
        return getGCD(b, a % b);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >>n;
 
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    cin >> k;
 
    for (int i = 0; i < k; i++)
    {
        for (int j = 0; j < (1 << n); j++)
            d[i][j] = -1;
    }
 
 
    for (int i = 0; i < k; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int init = i;
 
            for (int l = 0; l < arr[j].size(); l++)
            {
                init = (init * 10 + (arr[j][l] - '0')) % k;
            }
            na[i][j] = init;
        //    cout << na[i][j] << ' ';
        }
    //    cout << '\n';
    }
 
    
 
 
    ll ans = go(0, 0);
    ll can = 1;
 
    for (ll i = 2; i <= n; i++)
        can *= i;
 
 
 
 
    if (ans == can)
        cout << "1/1";
    else if (ans == 0)
        cout << "0/1";
    else
    {
        ll gcd = getGCD(can, ans);
        cout << (ans / gcd) << '/' << (can / gcd);
    }
}