BOJ - 1107번 리모컨(C++)

문제 출처: https://www.acmicpc.net/problem/1107

문제 난이도

Gold 5

문제 접근법

완전탐색의 기본적인 문제가 아닐까 싶다.
리모컨이 누를 수 있는 모든 버튼의 경우의 수를 찾아 가장 최소값을 출력해야한다.
N의 범위가 500,000이지만 N을 만들기 위해 누를 수 있는 값이 '999,999','1,000,000'가 있으므로 숫자 범위는 백만으로 해주고 모든 수를 찾는다.

통과 코드

#include <iostream>
#include <string>
#include <algorithm>


using namespace std;

int brokenCheck[10];

bool possible(string num) {
	for (int j = 0; j < num.size(); j++) {
		if (brokenCheck[num[j] - '0']) {
			return false;
		}
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int n;
		cin >> n;
		brokenCheck[n] = true;
	}

	int push = 0;
	int minV = 987654321;
	int size = 0;
	for (int i = 0; i < 1000001; i++) {
		string canPush = to_string(i);
		if (possible(canPush)) {
			push = abs(N - i);
			if (minV > push) {
				minV = push;
				size = canPush.size();
			}
		}
	}
	int ans1 = minV + size;
	int ans2 = abs(100 - N);

	cout << min(ans1, ans2) << "\n";


	return 0;
}

피드백

조금만.. 뇌를 힘주지 않으면 틀려버리는게 알고리즘이다. 똑바로 짜자!