[백준 C++] 1107번: 리모컨

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

 

리모컨을 움직여 주어진 채널로 옮길때 최소 경우의 수를 구하는 문제이다.

 

우선 숫자를 지웠을때 목표 채널까지 어떻게 하면 가장 가깝게 갈수 있을지 생각해봐야한다.

 

1. 지워진 숫자를 제외하고 가장 가까운 위치를 찾아야한다. 

1-1. 그후 도착하지 못하는 위치라면 +, - 버튼을 이용하여 움직인다.

 

2. +, - 버튼을 이용하여 움직인다.

 

브루트포스로 이 문제를 해결하였는데 0부터 500000까지 이동하는 경우의 수를 전부 계산하여 넣어준 뒤, 그 중 가장 가까운 결과만 남기는 방식으로 해결하였다.

 

하지만 n의 범위가 500000까지라고 해서 거기까지만 반복한다면 답을 못맞추는 경우가 있다. 예를들어 n = 500000일때, 사용가능한 숫자가 5와 1뿐이라면 511111에서 11111번 가야한다. 이전 조건으로 for문을 실행할 경우 약 100000번의 손실이 발생한다. 따라서 1000000까지 반복해주자.

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
bool btn[10] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
 
bool valid(int n) {
	if (n == 0) {
		if (btn[0]) return true;
		return false;
	}
	while (n) {
		if (!btn[n % 10]) return false;
		n /= 10;
	}
	return true;
}
 
int main(int argc, char* argv[])
{
	int n, m, ch = 100;
	
	cin >> n >> m;
 
	for (int i = 0;i < m;i++) {
		int b_btn;
		cin >> b_btn;
		btn[b_btn] = 0;
	}
 
	int ans = abs(ch - n);
 
	for (int i = 0; i <= 1000000; i++) {
		if (valid(i)) {
			int t = to_string(i).length();
			t += abs(i - n);
			ans = min(ans, t);
		}
	}
 
	cout << ans << '\n';
 
	return 0;
}

 

이러한 시스템을 처음 접해서 힘들었다. 다음에 비슷한 유형의 문제는 잘 풀 수 있을것 같다.