백준 1107. 리모콘

알고리즘 기초 문제 중 브루트포스 기초 문제(500)

리모콘

1. 간단 설명

리모콘에 버튼이 0~9까지, +, - 버튼이 있다

현재 채널이 100번

원하는 채널로 이동하려 할 때, 버튼을 최소로 눌러서 이동하려한다

그런데 일부 숫자 버튼이 고장나있음

2. 예시

5457
3
6 7 8

채널 5457로 이동하려하는데

6 7 8 버튼이 고장나있다

이 때 5455로 이동한 뒤 위로 두번 이동하던가

5459로 이동해서 아래로 두번 이동하는게 버튼 6번으로 처리 가능하다

100
5
0 1 2 3 4

현재 채널이 100번이므로 버튼 누를 필요 없음

3. 알고리즘

만약 내가 직접 리모콘을 사용한다고 생각하면

1. 먼저 해당 채널번호를 직접 눌러 시도해보기
2. 버튼이 고장난걸 확인하고 눌려지는 버튼들로 가장 가까운 채널로 이동
3. 이후 위 또는 아래 채널로 이동하기

이런식으로 이동할 것이다

그런데, 여기서 ‘가장 가까운 채널’을 어떻게 구할것인지가 어려움

그렇다면 컴퓨터의 힘을 빌어 완전탐색을 시도해본다면

채널 1에서 목표 채널로 가는데 버튼을 몇번 누를 것인가

채널 2에서 목표 채널로

채널 3에서 ..

이런식으로 모든 채널에서 해당 채널로 가는데 버튼을 몇번씩 눌러야하는지를 모두 계산해서

최소값을 구해본다

1. 먼저 최소값은 + 또는 -를 일일히 눌러 이동하는 회수로 초기화한다
	- 즉 현재 채널이 100번이므로, abs(목표 채널 - 100)번 만큼 눌러주어야한다
2. 이후, 채널 0번부터 확인한다
	2-1. 이 채널을 리모콘 버튼들로 이동할 수 있는지 체크
	2-2. 만약 이동할 수 있다면, 현재 버튼을 몇번 눌렀는지 센다
	2-3. 목표 채널과 얼마나 차이나는지를 센 뒤, 위에서 계산한 몇번 눌렀는지 센 숫자와 더한다
	2-4. 기존의 최소값과 비교하여 최소값을 갱신한다
3. 최소값을 출력한다

2번에서 0번부터 몇번 채널까지 체크해야하는지가 어려운데

문제에서는 채널은 무한하다고 주어져있다

이를 통해서 50만번 채널에서 위에서 내려오는 경우가 최단거리일 수도 있다는것 유추할 수 있다

예를들어

1234567890 이 고장 난 경우, 100번에서 시작,

목표 채널이 500,000인 경우는 올라가는게 499,900번으로 빠르다

그러나 위에서 아래로 내려오는게 더 빠른 경우가 존재한다

12345 789 만 고장나고, 6과0은 멀쩡한 경우,

목표 채널이 500,000인 경우는 600,000에서 내려오는게 10만번으로 499,000번보다 빠르다

즉, 채널 N으로 이동하기 위해서 50만보다 높은 채널에서 내려오는 경우가 존재할 수 있으므로,

50만 이상 채널에서도 시도해야한다

4. 소스코드

#include <bits/stdc++.h>

using namespace std;

bool button_broken[10]; // true : 고장, false : 작동함

// num 채널을 숫자로 만들 수 있는지 체크하는 함수
bool check(int num) {
	string str = to_string(num);
	for (int i = 0; i < str.size(); i++) {
		// str[i] 라는 숫자가 고장난 숫자가 라면 불가능 리턴
		if (button_broken[str[i] - '0'] == true) {
			return false;
		}
	}
	return true;
}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	int cur = 100, target;
	cin >> target;

	int M; cin >> M;
	for (int i = 0; i < M; i++) {
		int tmp; cin >> tmp;
		button_broken[tmp] = true;
	}

	// 1. +, -로 이동
	int cnt = abs(cur - target);

	// 2. 0~100만까지 채널을 누를 수 있는지 체크
	for (int i = 0; i <= 1000000; i++) {
		if (check(i)) {
			// 채널 i로 이동이 가능한 경우
			// i로 이동해서 +, -로 이동하는 회수만큼 추가 후 최소값 비교
			
			int pressed = to_string(i).size(); // 버튼 누른 회수는 i의 자리수 만큼임
			int diff = abs(target - i);

			cnt = min(cnt, pressed + diff);
		}
	}

	cout << cnt;

	return 0;
}