알고리즘 문제 풀이/BOJ
[백준 BOJ][C++]1107번 리모컨 풀이: 브루트 포스
영벨롭
2022. 3. 20. 17:39
https://www.acmicpc.net/problem/1107
1107번: 리모컨
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼
www.acmicpc.net
이 문제는 브루트 포스 알고리즘을 사용하여 해결하는 문제입니다.
우선, 현재 100번 채널에서 N 번 채널까지 이동하기 위해 버튼을 눌러야 하는 최대 횟수는 + 혹은 - 버튼만을 눌러야 하는 경우 입니다. 따라서 100-N의 절댓값이 최댓값이 됩니다.
브루트 포스 알고리즘을 사용하므로 0번부터 1씩 증가하며 차례대로 모든 경우를 탐색해야겠죠?
[풀이 과정]
1. 숫자 num이 고장난 버튼을 포함하고 있지 않은지 확인
2. 포함하지 않는다면 num에서 N번까지 이동 횟수
= abs(N-num) (+ 또는 - 버튼 누른 횟수) + 숫자 num의 길이 (숫자 버튼 누른 횟수)
3. 0 부터 1000000까지 1~2과정 반복, 이동 횟수가 최소인 값이 정답
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<string>
using namespace std;
int n;
int m;
bool dis[10] = { false, };
bool is_possible(int num) {
string s = to_string(num);
for (int i = 0; i < s.size(); i++) {
if (dis[s[i] - 48])
return false;
}
return true;
}
int main(void) {
int ans = 0;
cin >> n;
cin >> m;
for (int i = 0; i < m; i++) {
int d;
cin >> d;
dis[d] = true;
}
if (n == 100) {
cout << 0;
return 0;
}
ans = abs(n - 100);
for (int i = 0; i <= 1000000; i++) {
if (is_possible(i)) {
int temp = abs(n - i) + to_string(i).size();
ans = min(ans, temp);
}
}
cout << ans;
return 0;
}
반응형