C++ / 백준 / 1107 / 리모컨

문제

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

1107번: 리모컨

문제풀이

시작 채널은 100이기 때문에 + or - 버튼을 일일이 누른 횟수를 answer에 저장한다.

N길이를 구하고, N-1 길이의 첫수부터 N+1 길이의 마지막 수까지 돌면서 해당수를 판별한다.

N의 최댓값은 500,000 이므로 최대로 돌려봐야 하는 수는 N+1 길이의 끝수이거나 1,000,000이다.

먼저 길이를 구하고, N번호까지 리모컨을 누르는 횟수가 answer 값보다 적다면 현재 숫자 중 고장 난 버튼이 있는지 확인한다. 만약 없으면 answer값을 경신한다.

 

int GetSize(int num) {
	int len = 1;
	while (num / 10 > 0) {
		num /= 10;
		++len;
	}
	return len;
}

GetSize는 해당 숫자를 나눠서 몇 자리 숫자인지 구하는 함수이다.

 

bool Check(int num) {
	if (num == 0 && button[0] == false)
		return false;
	while (num > 0) {
		if (button[num % 10] == false) {
			return false;
		}
		num /= 10;
	}
	return true;
}

Check함수는 숫자를 분해하여 고장 난 버튼이 있어 해당 숫자를 못 누르는지 확인하는 함수이다.

 

 

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
vector<bool>button(10, true);

int GetSize(int num) {
	int len = 1;
	while (num / 10 > 0) {
		num /= 10;
		++len;
	}
	return len;
}

bool Check(int num) {
	if (num == 0 && button[0] == false)
		return false;
	while (num > 0) {
		if (button[num % 10] == false) {
			return false;
		}
		num /= 10;
	}
	return true;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N = 0, M = 0;
	int idx = 0;
	int num = 0;

	cin >> N >> M;

	for (idx = 0; idx < M; ++idx) {
		cin >> num;
		button[num] = false;
	}

	int answer = abs(N - 100);
	int start = 0;

	if (GetSize(N) > 2) start = pow(10, GetSize(N) - 2);
	int end = pow(10, GetSize(N) + 1);
	end = min(end, 1000001);

	for (idx = start; idx < end; ++idx) {
		if (abs(N - idx) + GetSize(idx) >= answer) continue;
		else if (Check(idx))
			answer = abs(N - idx) + GetSize(idx);
	}
	cout << answer;
}