생각이 많이 필요했던 브루트 포스 문제이다. 버튼을 최소 몇번 누르는지 구하는 문제였는데 여러 조건들이 떠오르면서 생각이 많아졌었다. 우선 채널의 시작은 100번이라는 것, 그리고 101, 99와 같이 +, - 만으로 가는게 더 빠른 경우, 그리고 버튼이 고장나 눌리지 않는 경우도 있다.
최소 숫자를 구해야 하기 때문에 우선은 최소 거리의 숫자와 N
의 절댓값 차를 구하면 된다고 판단했다. 브루트 포스 이기에 처음부터 끝까지 반복문을 돌려주려 했는데, 버튼이 5,6,7,8,9가 눌리지 않을 경우를 생각하면 최대 채널이 1,000,000이 되서 시간 초과가 나지 않을 까 걱정을 좀 했었다.
반복문을 돌면서 isTrue
함수로 해당 채널에 눌리지 않는 버튼 숫자가 포함되있는지 확인을 했고 없다면 채널 숫자의 번호 갯수와 N
과의 절대값 차를 구해 res
와 비교하여 작은 값을 저장해두었다. res
의 초기값은 abs(N-100)
으로 주었다.
생각이 많이 필요했고 최대 채널은 다른 분의 풀이를 참고했다.
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int N, M;
bool A[10];
bool isTrue(int n) {
string tmp = to_string(n);
for (int i = 0; i < tmp.size(); i++) {
if (A[tmp[i] - '0']) {
return false;
}
}
return true;
}
void solution() {
int res = abs(N - 100);
for (int i = 0; i < 1000000; i++) {
if (isTrue(i)) {
int a = abs(N - i) + to_string(i).size();
res = min(res, a);
}
}
cout << res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
cin >> M;
for (int i = 0; i < M; i++) {
int a;
cin >> a;
A[a] = true;
}
solution();
return 0;
}