개요
요즘은 알고리즘 풀이가 스트레스 풀이에 제격입니다.
뭔가 스트레스 풀이 수단으로 게임을 하면 시간을 낭비하는 것 같은데 알고리즘을 풀면 시간 낭비를 하는 것 같지 않아서 기분이 좋아요.
근데 모순되게도 이 문제는 풀면서 스트레스를 이만치 받았습니다.
문제
박성원은 이 문제를 풀지 못했다.
서로 다른 정수로 이루어진 집합이 있다. 이 집합의 순열을 합치면 큰 정수 하나를 만들 수 있다. 예를 들어, {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로 출력한다.
테스트 케이스
| 입력 | 출력 |
| 3 3 2 1 2 |
1/3 |
풀이
아이디어 정리
문제가 갑자기 중간에 변주를 줍니다.
단순히 K로 나누어 떨어지는 정수를 출력하란건줄 알았는데 찍어서 맞출 수 있는 확률 구하기 문제가 돼버렸네요.
아무튼 확률 자체는 매우 간단하게 구상 해낼 수 있습니다.
$$\frac{(정답의 개수)}{(만들 수 있는 수열의 개수)} = \frac{b}{a}$$
만들 수 있는 수열의 개수를 \(a\), 정답의 개수를 \(b\)이라고 둘게요.
일단 \(N\)개의 수가 들어왔을 때 서로 다른 수를 사용해서 만들 수 있는 모든 수열의 개수는 \(N!\)이죠.
이러면 분모는 구했습니다.
$$ a = n! $$
근데 분자를 구하는건 많이 까다로워요. 일단 문제에선 N은 15보다 작거나 같은 자연수라고 합니다.
일단 모든 순열을 탐색 하는건 \(O(N!)\)으로 일단 무리인걸 알 수 있죠.
저희가 중점적으로 봐야할 건 경우의 수가 \(O(N!)\)라서 그냥 브루트포스로 돌릴 수가 없다는거에요.
그래서 나머지가 K인 수만 골라서 효율적으로 세기 위해 DP를 사용해볼겁니다.
일단 단순한 DP로는 불가능하겠죠. 그래서 비트마스킹을 접목해보죠.
저희가 N개의 숫자중 일부를 사용해서 어떤 수열을 만들었다고 해봅시다. 다음 숫자를 선택해서 뒤에 이어붙이려고 할 때 최종적으로 완성된 수열이 K로 나누어떨어지는지 알려면 지금까지 어떤 숫자를 사용했는지를 알아야겠죠?
이 아이디어를 바탕으로 구상을 해보면 비트마스킹을 사용하는게 찰떡이란걸 알 수 있습니다.
이전에 풀었던 [백준] | C++ | 4991. 로봇 청소기 (TSP, 비트마스킹) 에서도 방문했던 노드를 기억하기 위해 비트마스킹을 사용했죠. 비유를 해보자면 이것도 정수 하나하나를 노드라고 취급해보는거죠.
비트마스킹을 사용하기 위해선 노드의 개수가 충분히 적어야하고, 지금 문제는 \(N\)의 최댓값은 15로 \(2^{15} = 32768\)이기 때문에 충분히 버틸만합니다.
아무튼 DP 하면 점화식이 나와야겠죠? 점화식을 세우기 전에 간단하게 무슨 값을 index로 사용하고 어떠한 값을 담을건지 적어봅시다.
간단하게 이런식으로만 해볼까요?
dp[mask] = m : mask 만큼 수를 사용하고 K로 나누었을 때 나머지가 0인 수열의 개수 m.
이걸로 충분할지 한번 생각해봅시다.
현재 mask인 상태에서 다음 숫자 num[i]를 추가한다고 해봅시다. 그러면 새로운 상태는 new_mask = mask | (1 << i)가 되겠죠. 이때 새로운 상태의 값을 계산하기 위해 단순히 이 정보만으로 충분할까요?
일단 DP는 현재 상태를 계산하기 위해서 이전 상태의 계산 결과를 사용하여 연산량을 줄이는게 핵심입니다.
dp[mask] 의 값을 dp[new_mask]를 계산할 때 사용을 할수야 있겠죠. 하지만 dp[new_mask]를 계산할 때 필요한 정보를 생각해보자구요.
저희가 mask 상태에서 숫자 j를 추가해서 new_mask 상태로 간다고 해봅시다. 저희는 mask 상태까지 만들었던 여러 수열이 있을거고 그 각각의 수열 뒤에 숫자 j를 붙여서 새로운 수열을 만들게 됩니다.
근데 여기서 저희는 당연하게도 mask 상태까지 만들었던 수열을 저장해둘 방법이 없습니다. 그래서 결국 j가 들어간 새로운 수열을 다시 계산해봐야 해요.
그러니 dp[mask] = m 같은 점화식은 이제 정보가 부족하다는걸 알 수 있습니다. 이대로 가면 그냥 모든 순열 탐색과 다를바가 없어지거든요.
그래서 이제 dp에 정보를 더 담아야하는데 여기서 잠시 나머지 연산의 특성에 대해 알아갈 필요가 있습니다.
나머지 연산에 대해
나머지 연산은 어떠한 수를 어떠한 수로 나누었을 때의 나머지를 구해주는 연산이라고 할 수 있어요.
응용이나 그런거는 글 취지에 맞지 않으니 넘어가봅시다.
수 3과 2를 둬봅시다. 그리고 3에 2를 붙인 32를 4로 나눈 나머지를 구해볼까요?
방법은 많습니다. 하나는 그냥 직접 계산해보는거에요.
32 / 4는 8이고 나머지는 0입니다. 쉽죠?
두번째 방법은 그 특성을 응용하는겁니다.
저희가 이미 3을 4로 나눈 나머지를 알고 있다고 해봅시다. \(3\bmod 4 = 3\)
그리고 붙일 숫자인 2를 4로 나눈 나머지도 알고 있어요. \(2\bmod 4 = 2\)
그리고 3 뒤에 2를 붙이는건 수학적으로 다음 식과 같죠? \(3 \times 10 + 2\)
그러면 이제 \(32 \bmod 4\), 그리고 \((3 \times 10 + 2) \bmod 4\)가 똑같다는걸 알 수 있어요.
그 뒤에 나머지 연산의 성질에 따라 덧셈과 곱셈을 각각 분리할 수 있습니다.
\(((3 \times 10) \bmod 4 + (2 \bmod 4)) \bmod 4\)
\(= (((3 \bmod 4) \times (10 \bmod 4)) \bmod 4 + (2 \bmod 4)) \bmod 4\)
이제 여기서 저희가 아는 값들을 대입해볼겁니다.
\(((3 \times 2) \bmod 4 + 2 \bmod 4) \bmod 4\)
\(= (6 \bmod 4 + 2) \bmod 4\)
\((2 + 2) \bmod 4 = 4 \bmod 4 = 0\)
대충 이런식으로 나머지 연산을 풀고 풀어서 계산할 수 있어요.
제가 하고싶은 말은 3의 나머지와 2의 나머지, 그리고 자릿수를 맞추기 위해 곱해진 10의 나머지만 알 수 있으면 나머지 연산을 능히 할 수 있다는거에요.
구체적인 수 없이 나머지 연산을 할 수 있다니 얼마나 좋습니까, 그죠?
그래서 그 나머지 값을 DP의 상태 값으로 사용할겁니다.
점화식 세우기
식을 개선해봅시다.
dp[mask][mod] = m : mask 만큼의 수를 사용하고 K로 나누었을때 나머지가 mod인 수열의 개수 m.
어느정도 충분한 것 같죠?
이제 점화식을 세우면 끝이에요.
mask에 해당하는 숫자들을 사용해서 K로 나눈 나머지가 mod인 수열이 dp[mask][mod]개 있다는걸 알고 있죠?
이 상태에서 아직 사용하지 않은 숫자 num[i]를 선택해서 뒤에 이어 붙인다고 해봅시다.
새로운 마스크인 new_mask는 mask | (1 << i) 겠죠. 이전에 똑같은 식이 있었으니까요.
그러면 이제 새로운 상태인 new_mod의 계산식은 이런식이겠죠.
new_mod = (mod * ((10 ^ num[i]의 길이) % K)) % K + num[i] % K) % K
(얘는 LaTeX를 쓰질 못해요. mod를 변수명으로 설정하다보니까...)
dp[mask][mod]는 mask, mod 상태까지 도달 할 수 있는 경우의 수를 나타내므로 이 상태에서 다음 숫자 num[i]를 선택하여 new_mask, new_mod 상태로 전이할 때 dp[mask][mod]만큼의 경우의 수가 dp[new_mask][new_mod]에 누적되어야 합니다.
그러므로 최종 점화식은 dp[new_mask][new_mod] += dp[mask][mod] 가 되게 됩니다.
코드로 적기
점화식이 나왔으니 이제 코드만 적어줍시다.
N과 K, 그리고 DP 배열, 들어오는 수의 배열을 선언해줍니다.
들어오는 수는 50자리 까지 가니 웬만한 정수형으론 꿈도 꿀 수 없습니다.
그래서 이제 수를 담는 배열은 예외적으로 string으로 선언해줍니다.
int N, K;
long long dp[1 << 15][101];
string nums[16];
그리고 이제 입력을 받아줍시다.
cin >> N;
for (int i = 0; i < n; i++)
cin >> nums[i];
cin >> K;
dp[0][0] = 1;dp[0][0]은 1로 초기화해줍니다.
여기서 이제 문제는 저희가 문자열로 들어온 엄청나게 큰 수를 나머지 연산 해줘야 한다는거에요.
근데 이것도? 저희가 이전에 짚었던 나머지 연산의 특성으로 해결할 수 있습니다.
바로... 이렇게요.
int getMod(string& str)
{
int res = 0;
for (int i = 0; i < str.length(); ++i)
{
int digit = str[i] - '0';
res = (res * 10 + digit) % k;
}
return res;
}
뭐 아무튼 이것까지 했으면 저희가 최종적으로 구해야하는 값은 dp[(1 << n) -1][0] 에 담겨 있으니 이제 dp배열을 순차적으로 채워나가기만 하면 됩니다.
그 전에 몇가지 전처리를 해봅시다.
연산 중 사용될 값을 미리 연산해두고 갖다 써야 연산량을 줄일 수 있습니다.
특히 이 \(10^n \bmod k\) 같은 경우엔 매 연산마다 사용되는데 값은 똑같으니 미리 캐싱해두는게 좋습니다. 또한 들어온 숫자의 K로 나눈 나머지 값도 미리 연산해서 저장해두는게 좋겠죠?
그런 의미에서 다음과 같은 값을 담을 배열을 만들어줍니다.
int num_mods[16];
int ten_mods[51];
그리고 캐싱해주면 되죠.
for (int i = 0; i < N; i++)
num_mods[i] = getMod(nums[i]);
ten_mods[0] = 1 % K;
for (int i = 1; i <= 50; ++i)
ten_mods[i] = (ten_mods[i - 1] * 10) % K;쉽죠? ten_mods는 DP네요.
이번엔 mask가 0부터 (1 << n) -1까지 증가해야하니 Top-down 대신 Bottom-up을 사용해볼겁니다.
이런식으로 2중 for문을 준비해줍니다.
for (int mask = 0; mask < (1 << N); mask++)
{
for (int mod = 0; mod < K; mod++)
{
// 여기다가 코드 적을거임
}
}
그리고 만약 mask와 mod 상태에서 경우의 수가 존재하지 않다면 스킵합니다.
if (dp[mask][mod] == 0)
continue;
그리고 안에서 for문 하나를 더 돌아주면서 위에서 세웠던 계산식을 바탕으로 코드를 짜줍니다.
for (int i = 0; i < N; i++)
{
if (!(mask & (1 << i))) //만약 i번째 수가 mask에 포함되어 있지 않다면
{
int new_mask = mask | (1 << i);
int new_mod = (mod * ten_mods[nums[i].size()] % K + num_mods[i]) % K;
dp[new_mask][new_mod] += dp[mask][mod];
}
}
여기까지 하면 이제 dp[(1 << N) - 1][0] 에 정답을 찍어서 맞출 수 있는 경우의 수가 들어갑니다.
그리고 분모가 될 \(N!\)을 구하기 위해 factorial 함수를 적어줍니다.
N의 최댓값은 15기 때문에 long long으로 충분히 버틸 수 있습니다.
long long factorial(int x)
{
long long res = 1;
for (int i = 2; i <= x; i++)
res *= i;
return res;
}
그렇게 이제 분자와 분모를 모두 구했죠.
long long x = dp[(1 << N) - 1][0];
long long y = factorial(N);
근데 문제에선 뭐라고 말하고 있죠?
첫째 줄에 정답을 기약분수 형태로 출력한다.
근데 지금 짠 코드는 어떻죠?
아뿔싸, 기약분수가 아니군요. 저 답들을 기약분수로 만들어주기 위해 유클리드 호제법을 사용한 최대공약수를 구하는 함수를 만들어줍니다.
long long gcd(long long x, long long y)
{
if (y == 0)
return x;
return gcd(y, x % y);
}
그리고 이 값을 바탕으로 각각의 x와 y를 나눠주고 출력하면 됩니다.
long long g = gcd(x, y);
cout << x / g << "/" << y / g;
마치는 말
솔직히 이거 플레 5 아니에요. 절대 아님. 아무튼 아님. 플레에 올라갈 때 풀었던 1557.제곱 ㄴㄴ보단 쉬웠는데 솔직히 10999.구간 합 구하기 2보다 어려워요.
플레 3은 가야할 것 같습니다. 아무튼 그래요.
코드 전문
#include <bits/stdc++.h>
using namespace std;
#define FAST_PRINT std::ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define BEGIN_TO_END(vec) vec.begin(), vec.end()
#define MEMSET(arr, i) memset(arr, i, sizeof(arr))
int N, K;
long long dp[1 << 15][101];
int num_mods[16];
int ten_mods[51];
string nums[16];
int getMod(string& str)
{
int res = 0;
for (int i = 0; i < str.length(); ++i)
{
int digit = str[i] - '0';
res = (res * 10 + digit) % K;
}
return res;
}
long long factorial(int x)
{
long long res = 1;
for (int i = 2; i <= x; i++)
res *= i;
return res;
}
long long gcd(long long x, long long y)
{
if (y == 0)
return x;
return gcd(y, x % y);
}
int main()
{
FAST_PRINT;
MEMSET(dp, 0);
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> nums[i];
}
cin >> K;
dp[0][0] = 1;
for (int i = 0; i < N; i++)
num_mods[i] = getMod(nums[i]);
ten_mods[0] = 1 % K;
for (int i = 1; i <= 50; ++i)
{
ten_mods[i] = (ten_mods[i - 1] * 10) % K;
}
for (int mask = 0; mask < (1 << N); mask++)
{
for (int mod = 0; mod < K; mod++)
{
if (dp[mask][mod] == 0)
continue;
for (int i = 0; i < N; i++)
{
if (!(mask & (1 << i)))
{
int new_mask = mask | (1 << i);
int new_mod = (mod * ten_mods[nums[i].size()] % K + num_mods[i]) % K;
dp[new_mask][new_mod] += dp[mask][mod];
}
}
}
}
long long x = dp[(1 << N) - 1][0];
long long y = factorial(N);
if (x == 0)
{
cout << "0/1";
return 0;
}
long long g = gcd(x, y);
cout << x / g << "/" << y / g;
}'알고리즘 > C++' 카테고리의 다른 글
| [백준] | C++ | 1557. 제곱 ㄴㄴ (포함-배제의 원리) (5) | 2025.04.29 |
|---|---|
| [백준] | C++ | 10942. 펠린드롬? (Top-down DP) (2) | 2025.04.20 |
| [백준] | C++ | 4991. 로봇 청소기 (TSP, 비트마스킹) (1) | 2025.04.19 |
| [백준] | C++ | 7453. 합이 0인 네 정수 (2) | 2025.04.11 |
| [백준] | C++ | 17626. Four Squares (0) | 2025.04.05 |