Problem 1107

리모컨

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

문제 링크

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

예제 입력 1

5457
3
6 7 8

예제 출력 1

예제 입력 2

100
5
0 1 2 3 4

예제 출력 2

예제 입력 3

500000
8
0 2 3 4 6 7 8 9

예제 출력 3

11117

solve

부르트 포스 알고리즘을 이용해 가능한 모든 채널을 확인하며 현재 채널이 숫자 버튼으로 이동이 가능한지 체크한다.
- 이동이 가능하다면 이후 +나 -버튼만으로 이동하는 횟수를 계산하여 모든 경우의 최솟값을 구한다.

최소한의 버튼을 누르는 횟수로 원하는 채널로 이동하려 한다면
- 숫자 버튼을 누른 후 +나 -중 하나만 연속해서 눌러 원하는 채널까지 이동해야 한다.
그럼 숫자 버튼을 눌러 이동하는 채널 c의 범위는 몇일까? 0 ~ 500,000이면 될 것 같지만 아니다.
예를 들어, 7빼고 모든 버튼이 고장났는데 이동하고 싶은 채널이 500,000이라고 한다면,
- 100에서 500,000 까지 +버튼만 눌러서 이동하기 위해서는 499,900번 눌러야 하지만 채널은 무한대이기 때문에
- 777,777로 이동하기 위해 6번 숫자7 버튼을 누르고 277,777번 -를 누르는 것이 최솟값이다.
따라서, c는 넉넉하게 100만까지 잡아주는 것이 좋을 것이다.
그렇다면 이후에 숫자 버튼을 이용해 채널 c로 이동한 다음 (0<=c<=1,000,000)
거기서 +나 -버튼을 몇 번 눌러야 하는지 계산을 해본다.
+나 -를 누르는 횟수는 현재 c값(현재 숫자 버튼으로 이동한 채널)에서 목표 채널을 빼고 절댓값을 취하면 된다.

이동할 채널 c를 정한다.
c에 포함된 숫자 중에 고장난 버튼이 있는지 확인한다.
고장난 버튼이 포함되어 있지 않다면 |c-n|을 계산하여 +나 -버튼을 몇 번 눌러야 하는지 계산한다.

코드 설명


#include<iostream>

using namespace std;
bool broken[10];

int possible(int c)
{
	int len = 0;
	if (c == 0) // 0일때 예외처리(c가 0으로 넘어왔다면 아래의 while문에 들어가지 않으므로 따로 처리)
	{
		if (broken[c]) return 0;
		else return 1;
	}
	while (c > 0)
	{
		if (broken[c % 10]) return 0; // 부서진 버튼이 있는 경우 false리턴
		c /= 10;
		len++; // 채널의 길이
	}
	return len; // 부서진 버튼이 없는 경우 채널의 길이를 리턴
}

int main(void)
{
	int n, m; // 채널 : n, 고장난 버튼 개수 : m
	cin >> n >> m;

	while(m--)
	{
		int temp;
		cin >> temp;
		broken[temp] = true; // 고장난 버튼은 true
	}

	int ans = n - 100; // 초기값 지정 n이 101이나 102같은 경우
			// 숫자 버튼으로 이동하는 것보다 + 나 - 만으로 이동하는 것이 최소이기 때문
	if (ans < 0) ans = -ans;

	for (int c = 0; c <= 1000000; c++)
	{
		int len = possible(c); // 부서진 버튼이 있다면 0, 없다면 채널의 길이
		if (len > 0)
		{
			int tmp = c - n; // 숫자로 이동한 채널에서 목표 채널과의 차이를 구함. 이것이 + or - 버튼으로 이동할 횟수
			if (tmp < 0) tmp = -tmp; // 절댓값
			if (ans > len + tmp) // len은 자릿수이므로 숫자를 누른 횟수
				ans = len + tmp; // 더 작다면 최솟값 변경
		}
	}

	cout << ans << '\n';

}

백준 1107번 리모컨

Baekjoon algorithm