Daily PS Comments #1

매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다.

완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요.

 

Digit Products

링크

• digit DP이긴 할텐데
• 곱을 직접 관리하기에는 $10^9$까지 커질 수 있으므로 무리가 있다
• 음.. 그냥 곱을 unordered_map의 인자로 관리하면 그건 되지 않을까?
• 어차피 소인수 분해 하고나면 대충 (2지수)×(3지수)×(5지수)×(7지수)만큼만 나오니까..
  • (3×18)×(2×18)×(18)×(18)의 상한을 갖는다
  • $6\times 18^4$면 꽤 합리적인 크기이다.
• 그럼 dp(자릿수 인덱스, 곱, tight)으로 관리하면 다 커버가 되나? 그럴듯
• for j>0, dp(i,j) = sum dp(i-1,j/k) for k=1..9
• dp(i,0) = $10^{i-1}$
• 느낌에 tight만 얹어서..

일단 ac 코드

#include <bits/stdc++.h>
using namespace std; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)

const int N = 21;
char s[N];
ll n, k, ans;
unordered_map<ll,ll> f[N], t[N];

int main() {
    cin >> &s[1] >> k;
    n = strlen(s+1);
    reverse(s+1,s+n+1);
    
    f[0][1]=t[0][1]=1;
    
    rep(i,1,n) rep(d,0,9) {
        for (auto &[j,v] : f[i-1]) {
            f[i][j*d] += v;
            if (d<s[i]-'0') t[i][j*d] += v;
            
            if (j*d<=k) {
                if (i<n&&d>0) ans += v;
                if (i==n&&0<d&&d<s[i]-'0') ans += v;
            }
        }
        for (auto &[j,v] : t[i-1]) {
            if (d==s[i]-'0')t[i][j*d] += v;
            
            if (j*d<=k) {
                if (i==n&&d==s[i]-'0') ans += v;
            }
        }
    }
    cout << ans;
}

 

현재 i가 leading zero가 아닌 경우를 차원 하나 더 담아서 수정하면 간단해진다:

#include <bits/stdc++.h>
using namespace std; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)

const int N = 21;
char s[N];
ll n, k, ans;
unordered_map<ll,ll> f[N][2], t[N][2];

int main() {
    cin >> &s[1] >> k;
    n = strlen(s+1);
    reverse(s+1,s+n+1);
    
    f[0][0][1]=t[0][0][1]=1;
    
    rep(i,1,n) {
        rep(d,0,9) rep(z,0,1) {
            for (auto &[j,v] : f[i-1][z]) {
                f[i][d>0][j*d] += v;
                if (d<s[i]-'0') t[i][d>0][j*d] += v;
            }
            for (auto &[j,v] : t[i-1][z]) {
                if (d==s[i]-'0') t[i][d>0][j*d] += v;
            }
        }
        for (auto &[j,v] : (i<n?f:t)[i][1]) {
            if (j<=k) ans += v;
        }
    }
    cout << ans;
}