[C/C++] 백준 - 1107번 : 리모컨

https://www.acmicpc.net/problem/1107

1107번: 리모컨

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

 

이 문제는 별 다른 알고리즘을 이용하여 해결하는 문제가 아닌 모든 경우의 수를 확인해서 최소값을 갱신해나가면 되는 문제이다. 문제의 시간제한이 2초로 꽤나 큰 시간이지만 주어지는 채널은 최대 500,000으로 그리 크지 않기 때문에 충분히 시간 내 해결이 가능하다.

 

나는 재귀로 모든 경우의 수를 확인해주었다.

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

string s;
int N,M,ps,cnt,sum,answer=INF;
bool isCan[10];
vector<int> channel;

void input() {
	cin >> s;
	cin >> M;
	N = stoi(s);
	for (int i = 0; i < M; i++) {
		int x; cin >> x;
		isCan[x] = true;
	}
}

void func(int index) {
	if (index == s.size() - 1) {
		ps = 1;
		sum = cnt = 0;
		for (int i = channel.size() - 1; i >= 0; i--) {
			sum += (channel[i] * ps);
			ps *= 10;
			cnt++;
		}
		answer = min(answer, abs(sum - N) + cnt);
	}
	if (index == s.size()) {
		ps = 1;
		sum = cnt = 0;
		for (int i = channel.size() - 1; i >= 0; i--) {
			sum += (channel[i] * ps);
			ps *= 10;
			cnt++;
		}
		answer = min(answer, abs(sum - N) + cnt);
	}
	if (index == s.size()+1) {
		ps = 1;
		sum = cnt = 0;
		for (int i = channel.size() - 1; i >= 0; i--) {
			sum += (channel[i] * ps);
			ps *= 10;
			cnt++;
		}
		answer = min(answer, abs(sum - N)+cnt);
		return;
	}

	for (int i = 0; i <= 9; i++) {
		if (!isCan[i]) {
			channel.push_back(i);

			func(index + 1);

			channel.pop_back();
		}
	}
}

void solution() {
	answer = abs(N - 100);
	for (int i = 0; i <= 9; i++) {
		if (!isCan[i]) {
			channel.push_back(i);
			func(1);
			channel.pop_back();
		}
	}
	cout << answer << endl;
}

int main() {
	fastio;
	input();
	solution();

	return 0;
}