백준 1107번 리모컨

문제 이해

이동하고 싶은 채널 번호가 주어지면 그 채널까지 이동하는 데 리모컨 버튼을 최소 몇 번 눌러야 하는지를 구하는 문제다. 리모컨 버튼은 0에서 9까지의 숫자 버튼, -버튼, +버튼이 있고, 채널은 0부터 무한대까지 있다. 숫자버튼 중 몇 개의 버튼은 고장이 나 있을수도 있다. 현재 채널은 100이다.

 

이동하고 싶은 채널 N이 주어지면, 고장이 나지 않은 버튼의 조합으로 N과 같거나 가장 가까운 숫자를 만든 뒤, N채널까지 -나 +버튼을 통해 이동하는 것이 최소로 버튼을 누르는 방법이다. 

 

 

풀이 설명

주어진 버튼으로 N을 만들지 못하는 경우 가장 가까운 숫자를 만들어야 하는데, 어떻게 그걸 만드느냐가 문제다. 손으로 푸는 것처럼 숫자를 만들자니 고려해야 할 것들이 너무 많아 완전 탐색을 통해 해결했다.

 

N보다 큰 숫자에서 -버튼을 눌러 N 채널로 가는 것이 최소인지, N보다 작은 숫자에서 +버튼을 눌러 N채널이 가는 것이 최소인지, 아니면 100에서 N채널로 이동하는 것이 최소인지는 계산을 해 봐야 알 수 있다. 해결 방법은 다음과 같다.

 

1. 100에서부터 N채널까지 이동하는 데 몇 번 버튼을 눌러야하는지 계산해 answer에 저장한다.

 

2. N부터 1씩 증가시키며 해당 채널이 유효한 채널인지 (주어진 버튼을 통해 만들 수 있는지) 검사하고, 유효하면 탐색을 멈춘다. 그리고 그 채널까지 이동하는 것과 answer 중 더 작은 것을 answer에 저장한다.

 

3. N부터 1씩 빼며 해당 채널이 유효한 채널인지 검사하고, 유효하면 탐색을 멈춘다. 그리고 그 채널까지 이동하는 것과 answer 중 더 작은 것을 answer에 저장한다.

 

 

구현

// 1107 리모컨

#pragma warning(disable: 4996)

#include <iostream>
using namespace std;

int N;	// destination chanel
int M;	// no. of broken buttons
bool btn[10] = { 0 };	// has info. on whether a button is broken
int ans;	// answer
int diff;	// difference between 100 and N

int valid(int n) {
	int len = 0;
	do {
		if (btn[n % 10]) return 0;
		n /= 10;
		len++;
	} while (n > 0);
	return len;
}

void findBig(int n) {
	for (int i = 0; i < diff; i++) {
		int len = valid(n);

		if (len) {
			int res = len + n - N;
			ans = ans < res ? ans : res;
			break;
		}

		n++;
	}
	return;
}

void findSmall(int n) {
	for (int i = 0; i < diff && n >= 0; i++) {
		int len = valid(n);

		if (len) {
			int res = len + N - n;
			ans = ans < res ? ans : res;
			break;
		}

		n--;
	}
	return;
}

int main() {
	scanf("%d", &N);
	scanf("%d", &M);

	// all buttons are broken
	if (M == 10) {
		printf("%d", N - 100 >= 0 ? N - 100 : 100 - N);
		return 0;
	}

	// input info. on broken buttons
	for (int i = 0; i < M; i++) {
		int num;
		scanf("%d", &num);

		btn[num] = true;
	}

	ans = N - 100 > 0 ? N - 100 : 100 - N;
	diff = ans;

	findBig(N);
	findSmall(N - 1);

	// print the answer
	printf("%d", ans);

	return 0;
}

 

구현하며 오류가 있었던 부분들

1. N보다 더 큰 숫자를 구할때 최댓값을 정해두지 않으면 무한루프가 발생한다. (해결방법 참고)

 

만약 N이 130이라고 할 때, 130과 현재 채널 100의 차는 30이다. 그러므로 더 큰 숫자를 구할 때 숫자가 130 + 30 = 160이상이 되어버리면 의미가 없어진다. 100에서 -나 +만으로 이동하는 것이 더 최소인 방법이기 때문이다. 

 

그러므로 N + |(100과 N의 차)| 까지만 검사하도록 한다.

 

2. 채널이 유효한지 검사하는 함수(valid())에서 리턴값

0이 전달됐을 때 아무 값도 리턴되지 않는 문제가 있었다. 0이 전달될 경우도 생각해야 한다.

 

3. 주어진 버튼으로 N을 만들 수 있는 경우

N보다 큰 수와 작은 수를 찾는 것에만 집중하다 보니, N을 검사하는 부분을 빼먹었었다. 그래서 큰 수를 찾는 코드에서 검사를 N부터 시작했다.

 

4. 메인 함수의 리턴값

실수로 메인 함수에서 0이 아닌 값을 리턴해서 런타임 에러가 발생했었다. 메인함수는 0을 리턴해야만 한다.

 

문제 링크: www.acmicpc.net/problem/1107