BOJ 7117 - Sevens, twos and zeros

문제 링크 : https://www.acmicpc.net/problem/7117

문제 풀이 1

 직접 푼 풀이이다. 나올 수 있는 모든 숫자의 종류는 대략 3^20 이다. 이는 3486784401 으로 10^9 보다도 크기 때문에 모든 숫자에 대해서 다 해보는 것은 옳지 못하다.

 딱 문제와 같은 경우에 쓸 수 있는 방식이 Meet in the Middle 방식이다. 10자리씩 끊어서 생각을 하자. 10자리 수에 대해서 각각 mod n 값을 계산해서 저장해 두자. 특히 n의 제한이 500000이기 때문에 그냥 각 나머지에 대해서 그 나머지를 가지는 최솟값을 저장해 둘 수 있다. 
 이후 10자리 수에 대해서 10^10을 곱한 후에 mod n 을 취한 값이 x 라고 하자. 첫 10자리는 그대로 쓰고 뒷 열자리는 n-x 의 나머지로 저장되어있는 값을 선택하면 된다. 구현 또한 어렵지 않게 할 수 있으며, overflow 는 유의를 해야한다. 

문제 풀이 2

 아마도 intended 풀이이다. 어떤 수의 뒤에 0,2,7 을 붙이는 것은 각각 *10 *10+2 *10+7 의 효과를 주는 것이다. 핵심은 각각의 나머지 값을 노드로 바꿔서 생각하는 것이다. 그러면 맨 뒤에 0,2,7 중 하나를 붙이는 하나의 행동은 노드에서 다른 노드로 이동하는 것을 생각할 수 있으며, 이는 단방향 간선이 되므로 그래프가 완성된다. 미리 mod n에 대한 그래프를 만들어 놓은 후 2와 7번 노드에서 시작해서 다익스트라를 돌리면서 경로를 저장하면 문제를 해결 할 수 있다. 

코드 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef double dl;
typedef pair<dl,dl> pdi;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> piii;
 
#define ff first
#define ss second
#define eb emplace_back
#define ep emplace
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
//cout<<fixed;
//cout.precision(12);
 
struct poi{
    ll val,xx,yy;
};
 
vector<ll> vs;
ll n,m;
ll mod=998244353;
string s;
string t;
ll arr[1010101];
vector<ll> v[1010101];
pii mini={1e12,1e12};
ll val[1010101];
 
void ip(ll x){
    ll p=10000000000;
    if(x>p) return;
    vs.pb(x);
    ip(x*10);
    ip(x*10+2);
    ip(x*10+7);
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll i,j,k,a,b,c,d,e,f;
    cin>>n;
    ip(2);
    ip(7);
 
    sort(vs.begin(), vs.end());
    for(auto k:vs){
        if(k%n==0){
            cout<<k;
            return 0;
        }
        if(val[k%n]==0){
            val[k%n]=k;
        }
    }
 
    for(auto k:vs){
        ll p=(k%n)*10000000000;
        p=p%n;
        p=n-p;
 
        if(p==0){
            cout<<k<<"0000000000";
            return 0;
        }
        if(val[p]){
            ll dem=(ll)log10(val[p])+1;
            cout<<k;
            for(i=1;i<=10-dem;i++){
                cout<<0;
            }
            cout<<val[p];
            return 0;
        }
    }
 
    cout<<"NAV";
}