충격과 공포의 문제이다. 엄청 더럽게 if문 많이 해서 풀었는데 전혀 그런식으로 푸는 문제가 아니었다.
브루트 포스로 처음부터 끝까지 하나하나 확인하면서 가는 문제이다.
반례↓
1555
8
0 1 3 4 5 6 7 9
670
10
9
1 2 3 4 5 6 7 8 9
11
0
9
1 2 3 4 5 6 7 8 9
1
100000
9
0 1 2 3 4 5 6 7 8
6
2229
6
4 5 6 7 8 9
5
10
1
0
2
0
10
0 1 2 3 4 5 6 7 8 9
100
9
8
0 3 4 5 6 7 8 9
4
-> 11인 경우로 시작해야 한다.
-> 자릿수마다 확인하는 것 안된다.
0
3
0 1 2
4
-> 0 인 경우 log값 안나온다.
생각보다 간단한 알고리즘인데, 문제에서 주어진 최대 범위는 5000000이지만, 그 위에서 내려가는 경우를 생각해야 하기 때문에 실제적으로 범위는 1000000까지 잡아줘야 해요
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
vector<int> dp;
vector<bool> mal(10,false);
bool check(int now){
string s = to_string(now);
for(int i = 0; i <s.length();i++){
if(mal[s[i]-48]){
return false;
}
}
return true;
}
int main(){
int n,c;
cin>>n>>c;
int tmp;
for(int i = 0; i < c; i++){
cin>>tmp;
mal[tmp] = true;
}
string st = to_string(n);
int minimum = abs(n-100);
for(int i = 0; i <= 1000000; i++){
if(check(i)){
int tmp = abs(n-i)+to_string(i).length();
minimum = min(minimum,tmp);
}
}
cout<<minimum<<endl;
return 0;
}
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ] 2579 계단 오르기 (0) | 2021.07.31 |
---|---|
[BOJ] 2615 오목 (0) | 2021.07.15 |
[BOJ] 7573 고기잡이 (0) | 2021.07.14 |
[BOJ] 17255 N으로 만들기 (0) | 2021.06.23 |
[BOJ] 3933 라그랑주의 네 제곱수 정리 (0) | 2021.06.15 |