백준 1086 (C++) 박성원

최초 업로드: 2025-04-28 00:27:34

최근 수정 시간: 2025-07-25 08:58:25

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] 박성원

[문제 링크](https://www.acmicpc.net/problem/1086)

## 문제 설명

박성원은 이 문제를 풀지 못했다.

서로 다른 정수로 이루어진 집합이 있다. 이 집합의 순열을 합치면 큰 정수 하나를 만들 수 있다. 예를 들어, {5221,40,1,58,9}로 5221401589를 만들 수 있다. 합친수가 정수 K로 나누어 떨어지는 순열을 구하는 프로그램을 작성하시오.

하지만, 박성원은 이 문제를 풀지 못했다.

따라서 박성원은 그냥 랜덤하게 순열 하나를 정답이라고 출력하려고 한다. 이 문제에는 정답이 여러 개 있을 수도 있고, 박성원이 우연히 문제의 정답을 맞출 수도 있다.

박성원이 우연히 정답을 맞출 확률을 분수로 출력하는 프로그램을 작성하시오.

## 입력

첫째 줄에 집합의 수의 개수 N이 주어진다. N은 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 집합에 포함된 수가 주어진다. 각 수의 길이는 길어야 50인 자연수이다. 마지막 줄에는 K가 주어진다. K는 100보다 작거나 같은 자연수이다.

## 출력

첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다.

## 풀이
#### dp[num][visited]를 현재 만들어진 숫자를 num이고, 현재까지 방문한 조합이 visited일 때, 이 수로 만들 수 있는 나머지가 0인 수의 개수로 두고 풀었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

string s[15];
int n, k, arr[15], mult[15];
long long dp[100][1<<15];
// dp[num][visited] : 현재까지 연결한 수의 나머지가 num이고, 현재까지 탐색한 조합이 visited일 때 이것으로 만들 수 있는 나머지가 0인 수의 개수

long long dfs(int num, int visited) {
 if(visited+1 == 1<<n) return num%k==0;
 if(dp[num][visited]!=-1) return dp[num][visited];
 dp[num][visited]=0;
 for(int i=0;i<n;i++) {
 if(!(visited & (1<<i))) {
 int nextNum = (num*mult[i] + arr[i]) % k;
 dp[num][visited] += dfs(nextNum, visited | (1<<i));
 }
 }
 return dp[num][visited];
}

long long fact() {
 long long ret=1;
 for(int i=2;i<=n;i++) ret *= i;
 return ret;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 cin >> n;
 for(int i=0;i<n;i++) cin >> s[i];
 cin >> k;

for(int i=0;i<n;i++) {
 mult[i]=1;
 for(int j=0;j<s[i].length();j++) {
 arr[i] = (arr[i]*10 + s[i][j]-'0') % k;
 mult[i] = mult[i]*10%k;
 }
 }
 memset(dp, -1, sizeof dp);

long long cnt = dfs(0, 0);
 long long total = fact();
 long long gcdVal = gcd(cnt, total);
 cout << cnt/gcdVal << '/' << total/gcdVal;
}
```