문제
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
입력
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
출력
첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.
풀이
기본 비교 대상은 현재 채널 100에서 +, -만 눌러 이동하는 경우다. 하지만 숫자 버튼으로 어떤 채널을 직접 누른 뒤 남은 차이만큼 +, -를 쓰는 편이 더 이득일 수 있으므로, 직접 입력 가능한 가장 가까운 채널을 찾아야 한다.
코드에서는 목표 채널 N에서부터 거리 i = 0, 1, 2, ...로 바깥쪽을 넓혀 가며 N - i, N + i 두 채널을 차례대로 검사한다. 각 후보 채널의 모든 자릿수가 고장 나지 않은 버튼으로만 이루어져 있으면, 그 채널까지의 숫자 입력 횟수와 지금까지 벌린 거리 i를 합쳐 답 후보로 사용할 수 있다.
중간에 숫자 버튼이 전부 고장난 경우처럼 예외도 따로 처리한다. 마지막에는 이렇게 찾은 값과 abs(N - 100)을 비교해서 더 작은 쪽을 정답으로 고르면 된다.
코드
#include <iostream>
#include <string>
using namespace std;
void solve() {
string n;
int m, x, answer = 0;
cin >> n >> m;
bool button[10] = {};
for (int i = 0; i < m; i++) {
cin >> x;
button[x] = true;
}
if (n == "100") {
cout << answer << '\n';
return;
}
if (m == 10) {
cout << abs(stoi(n) - 100) << '\n';
return;
}
string s1, s2;
for (int i = 0; ; i++) {
bool is_ans = true;
s1 = to_string(stoi(n) + i);
if (stoi(n) - i > 0) {
s2 = to_string(stoi(n) - i);
}
else {
s2 = to_string(0);
}
for (char c2 : s2) {
if (button[c2 - '0']) {
is_ans = false;
break;
}
}
if (is_ans) {
answer += (int)s2.size();
break;
}
is_ans = true;
for (char c1 : s1) {
if (button[c1 - '0']) {
is_ans = false;
break;
}
}
if (is_ans) {
answer += (int)s1.size();
break;
}
answer++;
}
answer = min(answer, abs(stoi(n) - 100));
cout << answer << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}복잡도
- 시간 복잡도: 검사한 후보 범위를 , 자릿수를 이라 할 때 이다.
- 공간 복잡도: 고장난 버튼 배열만 사용하므로 이다.
마무리
리모컨 문제는 완전탐색이지만, 모든 채널을 다 보지 않고 목표 근처에서 바깥으로 넓혀 가는 식으로 줄일 수 있다. 결국 숫자로 직접 갈지, +/-만 쓸지 둘 중 더 싼 쪽을 고르면 된다.
