[백준 1107 - c++] 리모컨

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

1107번: 리모컨

 

매우 짜증나는 문제였다. 처음 든 생각은 쓸 수 있는 버튼으로 주어진 번호와 가장 가까운 숫자를 찾아내는 게 목표라고 생각했다. 그래서 주어진 번호를 자릿수를 어떻게 하다보면 될 줄 알았는데 결국 안되었다.

그래서 그 다음 생각해낸 방법이 그냥 주어진 번호부터 시작해서 1 씩 더하거나 빼면서 쓸 수 없는 버튼이 포함되어 있으면 넘어가고 누를 수 있는 번호면 멈춘 다음 그 번호를 입력하고 + 나 - 버튼을 누르는 횟수를 더하는 방식이다.

예를 들어 목표 채널이 5000번 이면 5001 5002 5003 으로 가면서 누를 수 있는 번호인가 확인하는 것이다. 물론 4999 4998 4997 쪽으로도 가면서 누를 수 있는 번호를 찾은 후 위로 갔을 때와 아래로 갔을 때 어떤 게 더 유리한지 비교 후 답을 고른다. 

결과적으로 성공하긴 했는데 처리해줘야 할 예외 사항이 엄청 많았다. 밑에 코드를 보면 알겠지만 처리해줘야 하는 예외사항을 적어보면

1. 목표 채널이 100 이면 시작을 100에서 하므로 못 누르는 번호가 있든 없든 0 을 출력해야 한다.

2. 만약 0~9 모든 번호를 누를 수 없으면 오로지 + - 를 눌러야 하는 횟수로 답을 정한다. 

3.  고장난 버튼이 없으면 번호를 눌러서 목표 채널로 이동하는 것과 + - 만 눌러서 목표 채널로 이동하는 것 중 더 적은 횟수를 답으로 고른다.

------ 여기까지는 위 아래로 숫자를 탐색해 나가기전에 미리 처리해서 답을 내주고 4번은 누를 수 있는 숫자를 탐색한 후에 

4. (주어진 번호보다 작은 누를 수 있는 번호 + +를 누르는 횟수) , (주어진 번호보다 큰 누를 수 있는 번호 + -를 누르는 횟수) , 그리고 (+ - 만 누르는 횟수) 3개를 비교해서 가장 작은 걸 찾아야 한다.

 

못 누르는 번호는 vector 를 하나 만들어서 거기에 저장하였고 주어진 번호를 일부러 string 으로 받아 find 함수로 못누르는 번호가 있는지 없는지 편리하게 찾았다. 

 

전체 코드이다.

#include <iostream>
#include <cstring>
#include <string.h>
#include <string>
#include <cmath>
#include <vector>
#include <numbers>
#include <math.h>
#include <algorithm>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <tuple>
#include <utility>
#include <typeinfo>
#include <iomanip>
#include <set>
#include <map>

using namespace std;

vector<char> v;

int main(void) {

	ios::sync_with_stdio(0);
	cin.tie(0);

	string n;
	int m;
	char k;
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> k;
		v.push_back(k);
	}

	if (n == "100") {
		cout << 0;
		return 0;
	}

	if (v.size() == 10) {
		cout << abs(100 - stoi(n));
		return 0;
	}
	
	if (m == 0) {
		if (n.length() < abs(stoi(n) - 100)) {
			cout << n.length();
		}
		else
			cout << abs(stoi(n) - 100);

		return 0;
	}

	string temp = n;
	int num = stoi(n);
	int flag = 0;
	int z = 0;
	while (z <= abs(stoi(n) - 100)) {
		for (auto c : v) {
			if (temp.find(c) != string::npos) {
				flag = 1;
				break;
			}
		}
		if (flag == 1) {
			num++;
			temp = to_string(num);
			flag = 0;
		}
		else {
			break;
		}
		z++;
	}
	
	string temp2 = n;
	int num2 = stoi(n);
	flag = 0;
	while (1) {
		for (auto c : v) {
			if (temp2.find(c) != string::npos) {
				flag = 1;
				break;
			}
		}
		if (flag == 1) {
			num2--;
			temp2 = to_string(num2);
			flag = 0;
		}
		else {
			break;
		}
	}
	
	int answer = min(num - stoi(n) + temp.length(), stoi(n) - num2 + temp2.length());

	if (answer < abs(stoi(n) - 100))
		cout << answer;
	else
		cout << abs(stoi(n) - 100);
}