[BOJ / 구현] 1107 리모컨

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

1107번: 리모컨

 

1107 리모컨

알고리즘 : 구현

반례가 상당히 많은 구현 문제입니다. 예외처리를 잘 해주어야하는데 그렇기 때문에 정답률 또한 낮은 문제입니다.

구현 난이도 자체는 낮은 편이라 코딩 테스트에 나온다면 킬러 문제가 될거라고 생각됩니다.

0에서 일어나는 버그가 많아 참고하시길 반례 남기겠습니다.

 

반례

1
9
0 1 2 3 4 5 6 7 8 
9

0
4
0 1 2 3
5

 

 

 

< CODE >

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

bool broken[10];

int main() {
	int n, m;

	cin >> n >> m;

	int result = abs(n - 100);

	for(int i =0 ;i < m; i++){
		int num;

		cin >> num;

		broken[num] = true;
	}

	if (m == 10) {
		cout << abs(n - 100) << '\n';
		return 0;
	}

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

	for (int i = 0; i <= 500000; i++) {
		int num = n - i;
		int length = 0;
		bool a = false;

		if (num >= 0) {
			if (num == 0)
			{
				if (!broken[0]) {
					result = min(result, 1 + abs(n));
					break;
				}
			}
			else {
				a = true;

				while (num > 0 && a) {
					a = !broken[num % 10] && a;
					num /= 10;
					length++;
				}

				if (a) {
					result = min(result, length + abs(n - i - n));
					break;
				}
			}
		}

		num = n + i;
		length = 0;
		a = false;

		if (num != 0 && num <= 1000000) {
			a = true;
			while (num > 0 && a) {
				a = !broken[num % 10] && a;
				num /= 10;
				length++;
			}

			if (a)
			{
				result = min(result, length + abs(n + i - n));
				break;
			}
		}
	}

	cout << result << '\n';

	return 0;
}

시간 : 4ms

 

태그 : #1107 리모컨 #BOJ 리모컨 #BOJ 1107 #리모컨 반례 #리모컨 코드 #1107 리모컨 반례