문제 링크 : 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번 노드에서 시작해서 다익스트라를 돌리면서 경로를 저장하면 문제를 해결 할 수 있다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
#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";
}
|
cs |
'코딩 > 백준 문제 풀이' 카테고리의 다른 글
BOJ 10169 - 안전한 비상연락망 (0) | 2022.08.26 |
---|---|
BOJ 3682 - 동치 증명 (0) | 2022.08.26 |
BOJ 8311 - Variable Subsequences (0) | 2022.08.19 |
BOJ 12430 - 생존자 (0) | 2022.08.16 |
BOJ 17670 - 난 (0) | 2022.08.14 |