알고리즘 문제 풀이6
알고리즘 문제 풀이 6
최근에 푼 재미있는 문제들을 포스팅 해보겠습니다.
BOJ 1530 금민수의 합
이 문제는 4와 7로만 이루어진 수를 금민수로 정의하고, $N$($\leq1,000,000,000$)이 주어지면 $N$을 금민수의 합으로 나타내는 방법을 찾는 문제입니다. 만일, 방법이 여러가지라면 수의 개수가 적은 방법을, 이러한 방법 또한 여러가지라면 사전순으로 최소인 방법을 찾아야 합니다.
우선 여러가지 관찰을 해봅시다.
첫번째로 주어진 수 $N$을 금민수들의 합으로 표현하는 것이 불가능한 경우가 있을까요?
네, 물론 있습니다. 작은 수에서 예를 들어보면 1, 2, 3, 5, 6, 9, 10 같은 수들이 있겠네요. 하지만 수가 작으면 brute force 로도 처리할 수 있으므로 우리는 충분히 큰 $N$이 금민수의 합으로 표현이 불가능한지가 궁금합니다.
사실 우리는 17이 금민수의 합으로 표현이 불가능한 가장 큰 수라는 것을 어렵지 않게 보일 수 있습니다. 왜냐하면,
18 = 4 + 7 + 7 19 = 4 + 4 + 4 + 7 20 = 4 + 4 + 4 + 4 + 4 21 = 7 + 7 + 7
이므로, 이후의 수들은 이 네 수들에 4를 적당히 더해서 모두 표현 가능하기 때문입니다.
두번째로 우리가 관심있는 것은 $N$을 금민수의 합으로 표현하기 위해 필요한 금민수의 개수의 최솟값입니다.
이 최솟값을 구하기 전에 이 값의 상한을 적절히 구해봅시다. 즉, ‘$N$을 표현하기 위해 금민수가 많아야 몇개 밖에 필요하지 않다’ 라는 결론을 먼저 내려봅시다.
정확한 개수는 재쳐두고 이 개수가 아주 커질수 있을까요? 그렇지 않습니다.
합이 $N$을 초과하지 않을 때까지 가장 큰 금민수를 더해가는 방식을 취하다가 적당히 작아진 순간에는 위에서 우리가 관찰한 것과 같이 18, 19, 20, 21 중 한 수에 4를 적절히 많이 더함으로써 만들어도 아주 적은 개수의 금민수의 합으로 $N$을 표현할 수 있다는 것을 알 수 있습니다.
실제로 제출을 해보면 이 상한을 10개로 두어도 통과가 되는 것을 확인할 수 있습니다.
그러면 우리가 원래 관심있었던 금민수의 최소개수를 어떻게 계산하면 좋을지에 대해서 고민해 봅시다. 우선 이러한 최소개수가 작다는 사실은 ‘사용한 금민수의 개수’를 dynamic programming 의 상태로 활용하기 좋아보입니다.
이로 부터 다음과 같은 dp를 떠올릴 수 있습니다.
dp(x, k, c) := $N$의 x번째 이후의 자리수들로 이루어진 수를 만들수 있는가? (단, k개의 금민수를 사용할 수 있으며, 이전 자리수를 계산하면서 올림되어 올라온 값이 c)
따라서 $N$이 금민수 k개의 합으로 표현될 수 있는지는 dp(0, k, 0) 의 값을 계산하면 알 수 있을 것입니다.
한편, transition 은 다음과 같이 해주면 됩니다.
- 사용할 수 있는 금민수의 개수가 감소한다.(제일 짧은 금민수가 길이가 x보다 짧은 경우)
- k개의 금민수의 x번째 자리수를 정한다.(각각 4 또는 7)
(자세한 것은 코드를 참조하세요.)
이런 방법으로 우리는 $N$을 금민수의 합으로 나타내기 위해 금민수가 최소 몇개 필요한지 알 수 있습니다. 이 개수를 mn 이라고 명명합시다.
이제 우리는 합이 $N$이 되는 mn개의 사전순 최소인 금민수들을 찾기만 하면 됩니다.
사전순 최소가 되기 위해서는 가능한 가장 작은 금민수를 사용해야 합니다. 따라서 모든 금민수를 작은 수부터 iterate 하면서 그 수를 사용하고 총 mn개를 사용하여 $N$을 만드는 방법이 있는지 여부를 알아낸 뒤 만약 가능하다면 그 수를 바로 사용하면 됩니다.
특정 수를 사용하면서 총 cnt개의 금민수를 사용하여 $N$을 만들수 있는가는 마찬가지로 위의 dynamic programming 을 사용할 수 있습니다.
위의 정의에서 $N$ 을 $N$ - (특정 수)로 바꾼뒤 dp(0, cnt - 1, 0) 의 값을 계산해주면 되기 때문입니다.
고정된 $N$에 대해서 dp를 수행하는 데에 $10^4$ 시간이 소요되며, 많아야 10가지의 $N$에 대해서 dp를 수행해야 하므로 총 O($10^5$) 정도의 시간에 문제를 해결할 수 있습니다.
아래는 위의 알고리즘을 구현한 코드입니다.
#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> D;
int cc[12][12][12];
int dp(int x, int k, int c) {
if(x == D.size()) return c == 0;
int &ret = cc[x][k][c];
if(ret != -1) return ret;
ret = 0;
if(k) ret |= dp(x, k - 1, c);
for(int i = 0; i <= k; i++) {
int t = 4 * i + 7 * (k - i) + c;
if(t % 10 == D[x]) {
ret |= dp(x + 1, k, t / 10);
}
}
return ret;
}
int solve(int n) {
D.clear();
int t = n;
while(t) {
D.push_back(t % 10);
t /= 10;
}
memset(cc, -1, sizeof(cc));
int s = 0, e = 10, p = -1;
while(s <= e) {
int m = (s + e)>>1;
if(dp(0, m, 0)) {
p = m;
e = m - 1;
}
else s = m + 1;
}
return p;
}
int main() {
vector<int> gold;
for(int i = 1; i <= 9; i++) {
for(int j = 0; j < (1 << i); j++) {
int x = 0;
int p = 1;
for(int k = 0; k < i; k++) {
if(j & (1 << k)) x += 7 * p;
else x += 4 * p;
p *= 10;
}
gold.push_back(x);
}
}
sort(gold.begin(), gold.end());
cin >> N;
int mn = solve(N);
if(mn == -1) {
printf("-1");
return 0;
}
int j = 0;
for(int i = 0; i < mn; i++) {
for(; j < gold.size(); j++) {
if(solve(N - gold[j]) == mn - i - 1) {
printf("%d ", gold[j]);
N -= gold[j];
break;
}
}
}
}