백준 1107번: 리모컨 (C++)

1. 문제 링크

1107번: 리모컨

2. 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	int soobin;
	int m, temp, cnt = 0;
	cin >> n >> m;
	if (m == 10) {
		cout << abs(100 - n);
		return 0;
	}
	vector<int> v;
	vector<int> result;
	for (int i = 0; i < m; i++) {
		cin >> temp;
		v.push_back(temp);
	}
	string s;
	//채널 이동 안 하고 100에서 시작하는 경우
	int min = abs(n - 100);
	for (int i = 0; i < 1000000; i++) {
		s = to_string(i);
		for (int j = 0; j < s.size(); j++) {
			if (find(v.begin(), v.end(), s[j] - '0')!=v.end()) {
				break;
			}
			if (j == s.size() - 1) {
			//겹치는 거 없음
				temp = s.size() + abs(i - n);
				min = min > temp ? temp : min;
			}
		}
	}
	cout << min;
	return 0;
}

3. 노트

3-1. 첫 번째 시도

우선 문제의 알고리즘 유형이 브루트포스인 것을 알고 시작하기는 했으나, 0번 채널부터 탐색하여 목표 채널과 가장 가까운 채널을 찾기에는 연산 시간이 터무니없을것이라고 생각하여, 나름의 규칙을 찾으려고 애썼다.
먼저 생각했던 것은, 2999번으로 이동할 때, 리모컨에서 2를 누를 수 있다고 해도 3000번으로 이동한 후 아래로 한 채널 이동하는 것이 이득이므로, 다음에 누를 숫자를 고려하여 이번에 누를 숫자를 정하고자 하였는데, 무수한 반례가 존재하였다.

3-2. Brute force로 해결

그러던 중 문제의 조건에서 이동하려는 채널의 최댓값은 500,000이고, 시간 제한은 2초여서
0번부터 채널을 하나씩 탐색한다고 해도, 최악의 경우에도 대략 1000000*7*9 번의 연산만이 필요하기 때문에,
일반적으로 1초에 1억 번의 연산을 할 수 있다고 가정했을 때 2초라는 시간은 해당 연산을 수행하기에 충분한 시간이므로, 결국 0번부터 (넉넉잡아) 1,000,000번까지 누를 수 있는 채널인지 하나씩 확인해 보는 것으로 코드를 바꿨다.
결과적으로 32ms로 넉넉히 주어진 조건을 충족할 수 있었다.