문제
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
입력
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
출력
첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
const int Max = 1000001;
const int btn = 11;
bool allCh[Max];
char brok[btn];
int Min(int, int, int);
int main() {
int N; // 수빈이가 이동하려고 하는 채널
cin >> N;
int M; // 고장난 버튼의 개수
cin >> M;
for (int i = 0; i < M; i++) {
cin >> brok[i]; // 고장난 버튼 입력 (문자형으로 입력 받음)
}
string num;
for (int i = 0; i < Max; i++) {
allCh[i] = true;
num = to_string(i);
for (int j = 0; j < M; j++) {
if (num.find(brok[j]) != string::npos) {
allCh[i] = false;
}
}
}
allCh[100] = true;
int rst1= Max, rst2= Max; // 왜 초기화를 해야할까..?
for (int i = N; i >= 0; i--) { // 목표값보다 작은 값 중 가장 목표값에 가까운 값 찾기
if (allCh[i]) {
rst1 = i;
break;
}
}
for (int i = N; i < Max; i++) {
if (allCh[i]) {
rst2 = i;
break;
}
}
cout << Min(abs(N - rst1) + to_string(rst1).length(), abs(N - rst2) + to_string(rst2).length(), abs(N-100));
return 0;
}
int Min(int a, int b, int c) {
int min= a < b ? a : b;
return min < c ? min : c;
}우선 고장난 버튼을 문자형으로 받고, 0부터 수빈이가 갈 수 있는 채널 MAX까지 모든 채널에 대하여 고장난 버튼의 숫자가 포함된 채널일 경우, false를 넣어 준다. 이 때, 100의 경우 처음 시작할 때 부터 설정되어 있는 값이므로 true로 설정해준다. 이는 나중에 100이 목표값일 때 고장난 버튼 0이 있는 경우를 방지하기 위함이다.(사실 나중에 N-100으로 한 번 걸려줘서 상관 없다,,)
그 뒤 목표값보다 작으면서 고장난 버튼이 포함되지 않는 가장 목표값에 가까운 값, 혹은 목표값보다 크면서 목표값에 가장 가까운 값, 혹은 100부터 일일이 눌러서 갈 때의 값 중 가장 적게 버튼을 누르는 것 중 하나를 고르면 된다.
<목표값 - 가까운 값> + 가까운 값 버튼 누르기
어려웠던 문제ㅠ
- 완전 탐색, 브루트 포스?
발생할 수 있는 모든 경우의 수를 무식하게 탐색한다는 뜻이다.
전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다.
- 브루트 포스의 장점
(1) 알고리즘을 설계하고 구현하기 매우 쉽다.
(2) 복잡한 알고리즘 없이 빠르게 구현할 수 있다.
- 브루트 포스의 단점
(1) 알고리즘의 실행시간이 매우 오래 걸린다.
(2) 메모리 효율면에서 매우 비효율적이다.
- 브루트 포스의 종류
→ 브루트 포스는 크게 선형구조와 비선형 구조로 나눌 수 있다.
(1) 선형 구조: 순차 탐색
(2) 비선형 구조: 백트래킹, DFS, BFS
