[백준 1107번] 리모컨

난이도: 골드 5

문제 링크: www.acmicpc.net/problem/1107

1107번: 리모컨

백준 1107번: 리모컨

처음에는 각 숫자 자리수별로 비교해서 가장 가까운 수를 찾는 방법으로 하려다가...

굉장히 비효율적이고 정확하지 않은 알고리즘이 완성되어서 (string으로 입력받은 N을 변환하는 등)

혹시...? 하고 접근해 본 브루트 포스 메소드로 성공적으로 푼 문제입니다.

 

아래와 같이 접근했습니다.

• 숫자 0~9에 대해, bool 타입의 isBroken array를 만듭니다. 입력받은 망가진 버튼들에 대해 true로 설정해 줍니다.
• 숫자 0~1,000,000까지 loop를 돌며, 다음을 수행합니다:
  • 모든 자릿수를 검사하여, 망가진 버튼을 하나라도 포함한다면 연산을 하지 않습니다.
  • 망가진 버튼을 하나도 포함하지 않는 수에 대해, 버튼을 누른 횟수 = 찾은 수 - 목표하는 채널 의 절댓값으로 합니다.
  • 버튼을 누른 횟수 + 찾은 수의 자릿수를 답으로 리턴합니다.
  • 100만까지 루프를 도는 이유는, 목표하는 채널보다 큰 수에서 시작하여 하강하며 접근할 때를 고려하기 위함입니다.

이 문제 이후로 백준에서 알고리즘 분류 표시 기능을 꺼 버리기로 했습니다.

평소에 백준에서 문제를 보고, 알고리즘 분류를 보고 나서 풀기 시작하는 게 언젠가 독이 될 수도 있겠다는 생각이 들었어요.

 

	#include <iostream>
	#include <algorithm>
	#include <cmath>
	using namespace std;
	int N, M;
	bool isBroken[10];
	int length_or_broken(int input) {
	if (input == 0) {
	if (isBroken[0])
	return 0;
	else return 1;
	}
	int result = 0;
	while (input > 0) {
	if (isBroken[input%10])
	return 0;
	result++;
	input /= 10;
	}
	return result;
	}
	int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
	int temp;
	cin >> temp;
	isBroken[temp] = true;
	}
	int result = abs(100-N);
	for (int i = 0; i <= 1000000; i++) {
	int temp = i;
	int length = length_or_broken(temp);
	if (length > 0) {
	int button_pressed = abs(temp-N);
	result = min(result, button_pressed + length);
	}
	}
	cout << result;
	return 0;
	}

view raw 1107번_리모컨.cpp hosted with ❤ by GitHub