[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 리모컨 (1107)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 리모컨 (1107)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 리모컨 (1107)

 

---

 

1107번: 리모컨

[ 문제 ]

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

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

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

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

[ 입력 ]

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

[ 출력 ]

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

 

---

[ 코드 ]

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

bool broken[10]; // 버튼이 고장났으면 true, 고장나지 않았으면 false

int possible(int c) {
	if (c == 0) { // 아래의 while문을 돌리기 위해, 0번으로 이동할대의 코드는 따로 작성
		if (broken[0])
		{
			return 0;
		}
		else
		{
			return 1;
		}
	}

	// 수를 10으로 계속해서 나누면서 하나씩 검사하는 방법
	int len = 0;
	while (c > 0) // 몫이 0이 되면 빠져나감
	{
		if (broken[c % 10]) // 10으로 나눈 나머지로, 뒤에서부터 숫자 하나씩 검증. (고장난 숫자가 있는지)
		{
			return 0; // 하나라도 고장난 숫자가 있다면 return 0
		}
		len += 1; // 고장나지 않았으면 +1
		c /= 10; 
	}
	return len; // len값은 눌러야 할 채널의 값 ex. 48695 -> 5번 (모두 고장나지 않았을 경우)
}


int main() {
	int N; // 이동하려는 채널
	cin >> N;
	int M; // 고장난 버튼의 개수
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int x;
		cin >> x;
		broken[x] = true; // 고장 난 것이면 true
	}

	// 이동해야 하는 수 (+혹은, -만 사용할 경우)
	int ans = N - 100; 
	if (ans<0)
	{
		ans = -ans;
	}

	// 채널 이동 + (+/-)만 사용하는 경우 이동하는 수
	for (int i = 0; i <= 1000000; i++)
		// 이동하려고 하는 채널 N : 0<=N<=500000
		// 1. 100 에서 +만 눌러서 갈 경우, 499900번 눌러줘야 함.
		// 2. 반대 방향에서 499900번 눌러서 500000에 도착 가능한 숫자는, 999900
		// 즉, C의 상한은 999900 (채널은 무한대까지 존재하기 때문 : 이동 가능한 채널만 정해져 있음)
		// 따라서 넉넉잡아서 100만으로 상한을 두고 코드 작성
	{
		int c = i; // 이동할 채널 c

		int len = possible(c);

		if (len > 0) // len이 0이면 고장난 버튼이 포함되어 있다는 것
		{
			int press = c - N;
			// press는 c로 채널을 이동한 후, +혹은 -를 하는 값을 만들기 위해

			if (press < 0) // press가 0보다 작으면 양수로 만들어주기 (이 값만큼 +나 -를 해야함)
			{
				press = -press;
			}
			if (ans > len + press) // ans(+,-만 사용하는 경우) > len+press(채널 이동 + (+,-)만 사용하는 경우)
			{
				ans = len + press; // 최소값 변경
			}
		}
	}
	cout << ans << '\n'; // 최소값 출력
	return 0;
}