ZIMBABWE (상, p. 320)

문제#

어떻게 풀었나?#

일단 이 문제는 자력으로 못품.

이틀을 고민했는데, m으로 나누어 떨어지는걸 어떻게 해결해야 할지 모르겠었음.

p. 323에 보면 웨브바짐 문제의 답을 찾는 완탐 알고리즘을 소개하고 있는데, PS입문자는 반드시 익혀야 할 부분인 것 같아 기록해본다.

size N인 정수 배열로 만들 수 있는 모든 숫자 중복 포함해서 출력하기
size N인 정수 배열로 만들 수 있는 모든 숫자를 중복없이 출력하기

2025년 11월 8일 드디어 풀었다. 화요일부터 풀기 시작했는데, 금요일에 AC받을 수 있었다.

책에 있는 코드는 보지 않았고, 1324%6 == 724%6 이라는 핵심 아이디어까지 본 다음 구현했다.

일단 완탐으로 모든 순열을 구하면서 최종적으로 만든 price가 e보다 작은 것의 개수를 세어준다.

그 다음 중복없이 순열을 구하도록 코드를 수정한다. 여기까지 진행하면, O(15!/2!2!2!2!)이 된다. 이 값은 여전히 수십억이기 때문에 시간안에 안들어 온다. 또 DP를 하려고 하니 중복되는 부분문제가 존재 하지 않는다. 여기까지 작성한 코드가 아래의 코드이다. 1번과 2번의 차이는 if(i>0 && d[i-1]==d[i] && !chk[i-1]) continue; 이 조건 한줄이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> v;
string e, d;
int m, n;
bool chk[16];
void dfs(string price) {
    if(price.size() == e.size()) {
        if(price < e) cout << price << "\n";
        return;
    }

    for(int i=0; i<e.size(); i++) {
        if(chk[i]) continue;
        if(i>0 && d[i-1]==d[i] && !chk[i-1]) continue; //이 조건이 중요하다.
        chk[i] = true;
        dfs(price + d[i]);
        chk[i] = false;
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        cin >> e >> m;
        d = e;
        sort(d.begin(), d.end());
        dfs("");
    }
    return 0;
}

아까 위에서 DP 얘기를 꺼냈는데, 중복문제는 없지만 DP스타일로 바꾸기 위해 chk 배열을 bit형태로 표현해본다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> v;
string e, d;
int m, n;
bool chk[16];
inline bool IsChk(int chkbit, int i) { return (chkbit >> i) & 1; }
inline void TogChk(int& chkbit, int i) { chkbit ^= (1 << i); }
void dfs(string price, int chkbit) {
    if(price.size() == e.size()) {
        if(price < e) cout << price << "\n";
        return;
    }

    for(int i=0; i<e.size(); i++) {
        if(IsChk(chkbit, i)) continue;
        if(i>0 && d[i-1]==d[i] && !IsChk(chkbit, i-1)) continue; //이 조건이 중요하다.
        TogChk(chkbit,i);
        dfs(price + d[i], chkbit);
        TogChk(chkbit,i);
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        cin >> e >> m;
        d = e;
        sort(d.begin(), d.end());
        dfs("", 0);
    }
    return 0;
}

여기까지는 쉬운데, 그 다음부터가 문제다. 위의 dfs()함수의 string을 memoization하기가 애매하다. std::map같은 자료구조를 쓴다 하더라도 아까 언급했듯이 중복되는 부분문제가 없으므로 DP로 풀 수 없는 상태다.

이 문제를 해결할 수 있는 가장 핵심적인 아이디어가 여기서 필요한데, 정답이 되는 순열중 m의 배수가 되는 것들만 구하라고 했기 때문에 이 문제를 DP로 풀 수 있다는걸 알아차려야 한다. 1324%6 == 724%6 == 124%6이다. 즉, price를 만들면서 다음 dfs() 호출시 인자로 넘겨줘야 하는 정보는 지금까지 만든 price를 m으로 나눈 나머지만 넘겨주면 되는 것이다.

예를 들어, e=”1324”, m=6이라 하자. 1324에서 dfs()로 현재 13까지 price를 만들었다 가정하면, 그다음 price로 2를 붙여줄 때 13이란 정보가 필요하지 않고, 13%6인 1이란 정보만 있어도 되는 것이다.

이 부분 때문에 중복되는 부분문제가 생기면서 DP로 문제를 풀 수 있게 된다.

하지만 여기서 끝이 아니다. 한 가지 더 고려해야 할 사항이 있다. 그것은 정답으로 구한 순열은 e와 같아선 안되는 부분이 문제다. 이 부분을 간과하면 실제로 출력해야 할 값과 거의 유사하지만 조금은 많은 수가 출력 될 것이다.

이건 현재까지 만든 price가 e와 계속 같았는지 아니면 그보다 작았는지 여부를 따지면 된다. e보다 큰 경우는 애초에 탐색하지 않으므로 이건 아예 구하지 않고 skip한다.

정답 코드#

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> v;
string e, d;
int m, n, fullchk;
inline bool IsChk(int chkbit, int i) { return (chkbit >> i) & 1; }
inline void TogChk(int& chkbit, int i) { chkbit ^= (1 << i); }
const int M = 1e9 + 7;
int dp[20][1 << 16][2];
int dfs(int idx, int rmd, int chkbit, int is_less) {
    if(chkbit == fullchk) {
        if(rmd == 0 && is_less) {
            return dp[rmd][chkbit][is_less] = 1;
        }
        return dp[rmd][chkbit][is_less] = 0;
    }

    int& ret = dp[rmd][chkbit][is_less];
    if(ret >= 0) return ret;

    ret = 0;
    int q = rmd * 10;
    bool is_same = !is_less;
    for(int i = 0; i < d.size(); i++) {
        if(IsChk(chkbit, i)) continue;
        if(i > 0 && d[i - 1] == d[i] && !IsChk(chkbit, i - 1)) continue; // 이 조건이 중요하다.
        if(is_same && d[i] > e[idx]) continue;

        TogChk(chkbit, i);
        q += d[i] - '0';
        ret += dfs(idx + 1, q % m, chkbit, (d[i] < e[idx]) | is_less);
        if(ret >= M) ret -= M;
        q -= d[i] - '0';
        TogChk(chkbit, i);
    }
    return ret;
}
int main() {
    string s;
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tc;
    cin >> tc;
    while(tc--) {
        cin >> e >> m;
        d = e;
        fullchk = (1 << e.size()) - 1;
        sort(d.begin(), d.end());
        memset(dp, -1, sizeof(dp));
        printf("%d\n", dfs(0, 0, 0, 0));
    }
    return 0;
}