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

문제 바로가기

1107번: 리모컨

---

문제

 

수빈이는 악력이 지나치게 쎈가보다. 리모컨을 다루다가 일부 숫자 버튼이 고장났다.

  - 숫자 버튼이 고장났다는 내용을 문제 다 풀고 글 쓰는 지금 알았다. +, -도 고려하는 줄 알고 assert까지 써가봐 확인했는데... 역시 문제를 몇 번은 꼼꼼히 읽는 버릇을 들여야겠다.

0~9번까지의 숫자, +, - 버튼이 있다. 수빈이는 N번 채널로 이동하고 싶다.

어떤 버튼이 고장났는지 주어질 때, 채널 N으로 이동하려면 최소 몇 번 버튼을 눌러야 하는지 알아보자.

ps. 나라면 리모컨 새로 샀다.

---

조건

0 ≤ N ≤ 500,000

0 ≤ M ≤ 10

---

접근

아래 경우를 나누어 생각을 해보았다.

1. 모든 숫자 버튼이 망가진 경우

  - '+', '-' 버튼 밖에 못 쓴다. 따라서 \(|N-100|\)을 출력한다.

2. N == 0인 경우

  - 사용할 수 있는 버튼 중 가장 작은 수 + 1을 출력한다. (한 번 누르고 - 계속 누르기)

3. 0만 쓸 수 있는 경우

  - N < 50인 경우 N + 1을, 그 외에는 \(|N - 100|\)을 출력한다.

  - 0을 누르고 +를 누르냐, 아니면 그냥 +, -를 누르냐의 차이

4. 일반적인 경우

  - 만들 수 있는 수 중 제일 작은 N보다 큰 수 G와 제일 큰 N보다 작은 수 S를 구한다.

  - \(min(G - N + digit(G), N - S + digit(S), N - 100)\)를 출력한다.

  - G에서 -를 계속 누르기, S에서 +계속 누르기, 그냥 +, -를 누르기 중 제일 적은 횟수를 찾는거다.

  - digit 함수는 자릿수를 반환한다.

코드보기:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define INF 987654321
#define EL "\n"

int digit(int n) {
	int d = 0;
	for (int i = n; i > 0; i /= 10)
		d++;
	return d;
}

int main() {
	FAST_IO;

	int N;
	int M;
	cin >> N >> M;

	char brokenButtons[10];
	for (int i = 0; i < M; i++)
		cin >> brokenButtons[i];
	
	// 1. All numbers is broken
	bool isAllBroken = true;
	for (int i = 0; i <= 9; i++) {
		bool isFound = false;
		for (int j = 0; j < M; j++)
			if ('0' + i == brokenButtons[j]) {
				isFound = true;
				break;
			}
		if (isFound == false) {
			isAllBroken = false;
			break;
		}
	}
	if (isAllBroken) {
		cout << abs(N - 100) << EL;
		return 0;
	}

	// 2. N == 0
	if (N == 0) {
		for (int i = 0; i <= 9; i++) {
			bool isFound = false;
			for (int j = 0; j < M; j++)
				if ('0' + i == brokenButtons[j]) {
					isFound = true;
					break;
				}
			if (isFound == false) {
				cout << i + 1 << EL;
				return 0;
			}
		}
	}

	// 3. Only 0 is available.
	bool isOnlyZero = true;
	for (int i = 1; i <= 9; i++) {
		bool isFound = false;
		for (int j = 0; j < M; j++)
			if ('0' + i == brokenButtons[j]) {
				isFound = true;
				break;
			}
		if (isFound == false) {
			isOnlyZero = false;
			break;
		}
	}
	if (isOnlyZero) {
		if (N < 50)
			cout << 1 + N << EL;
		else
			cout << abs(N - 100) << EL;
		return 0;
	}

	// 4. General
	// 4-1. A Smallest number of numbers greater than N.
	int greater= N;
	while (true) {
		for (int i = greater; i > 0; i /= 10) {
			for (int j = 0; j < M; j++) {
				if ('0' + i % 10 == brokenButtons[j]) {
					greater++;
					goto CONTINUE_G;
				}
			}
		}
		break;
	CONTINUE_G:;
	}
	// 4-2. A Greatest number of numbers smaller than N.
	int smaller = N;
	while (true) {
		for (int i = smaller; i > 0; i /= 10) {
			for (int j = 0; j < M; j++) {
				if ('0' + i % 10 == brokenButtons[j]) {
					smaller--;
					goto CONTINUE_S;
				}
			}
		}
		break;
	CONTINUE_S:
		// PS. When smaller is useless.
		if (smaller == 0) {
			smaller = -INF;
			break;
		}
	}
	// 4-3. Get minimum and print
	int result = min(min(greater - N + digit(greater), N - smaller + digit(smaller)), abs(N - 100));
	cout << result << EL;

	return 0;
}

결과: 틀렸습니다.

---

분석

임의의 테스트케이스를 만들어서, 다른 블로그에 올라와 있던 정답코드와 출력을 대조했다.

  * N = rand() % 500001, 고장난 버튼은 boolean 배열로 만들어 각 값을 rand() % 2로 지정했다.

백만개 정도의 테스트 케이스를 돌려보니, 반례를 찾았다.

 

이를 확인한 후 CONTINUE_S 레이블 이하 코드를 지우고, digit 함수에서 0이 들어오면 1을 리턴하도록 수정했다. 왜냐하면, smaller가 0이 되는 경우는 불필요한 경우로 치부하여 -INF 값을 대입했는데, 이 경우가 필요한 때가 있었기 때문이다. 이를 수정한 후, 100만개의 테스트 케이스를 랜덤 생성하여 정답 코드와 출력을 3번 정도 더 했고, 이상이 없어서 제출했으나... 틀렸습니다.

 

아무리 랜덤 데이터라고 하지만, 모든 경우를 테스트할 수는 없었다. 입력 데이터로 주어질 수 있는 모든 경우의 수는...⁋

$$500,000\times\sum_{i=1}^{10}\left(\begin{array}{c}10\\ i\end{array}\right)=511500000$$

정답 코드의 시간복잡도는 \(O(n)\)정도 되고 25,000개의 입력을 처리하는데 1분이 소요됐으니, 이를 모두 연산하려면 341시간 정도 소요될 수 있을 정도의 많은 입력이다. 출력 데이터도 너무 방대해서 텍스트 대조 프로그램도 제대로 돌아가지 못 할 것이다. 따라서 입력 데이터를 반례가 등장할 확률이 높은 구간으로 설정하기로 했다.

$$0\leq{N}\leq{200},\text{ }499800\leq{N}\leq{500000}$$

각 N마다 고장날 수 있는 숫자 버튼의 모든 조합 1023가지를 모두 입력 데이터로 만들었다. 그렇게 만들어진 입력 데이터의 수는 무려 411648개. 연산을 마치는 데에만 20분 정도가 소요됐다.

입력 데이터 생성 코드:

#include <iostream>
#include <vector>

using namespace std;

#define EL "\n"

vector<vector<int>> combinations;
int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
bool select[10];

int N;

void combination(int idx, int cnt) {
	if (cnt == N) {
		vector<int> c;
		for (int i = 0; i < 10; i++)
			if (select[i])
				c.push_back(arr[i]);
		combi.push_back(c);
		return;
	}
	for (int i = idx; i < 10; i++) {
		if (select[i]) continue;
		select[i] = true;
		combination(i, cnt + 1);
		select[i] = false;
	}
}

int main() {

	freopen("C:\\Users\\**\\source\\repos\\**\\**\\input.txt", "w", stdout);

	cin.tie(NULL);
	ios::sync_with_stdio(false);

	vector<int> v;
	combinations.push_back(v);
	for (N = 1; N <= 10; N++) {
		combination(0, 0);
	}

	cout << 411648 << EL;
	for (N = 0; N <= 200; N++) {
		for (auto& c : combinations) {
			cout << N << " ";
			cout << c.size() << " ";
			for (auto& number : c)
				cout << number << " ";
			cout << EL;
		}
	}
	for (N = 499800; N <= 500000; N++) {
		for (auto& c : combinations) {
			cout << N << " ";
			cout << c.size() << " ";
			for (auto& number : c)
				cout << number << " ";
			cout << EL;
		}
	}
    
	return 0;
}

출력 데이터가 방대하여 일반적인 텍스트 비교 프로그램은 못 썼고, Beyond Compare라는 프로그램을 썼다.

데이터를 불러오고 수 초의 로딩 후 찾아난 반례가 아래다. 아래가 정답 코드로 돌린 결과다.

---

결과

상당히 감격스러웠다. 보아하니 문제는 smaller의 0에 대한 처리였다. 위에서 digit 함수에서 0이 들어오면 1로 반환하라고 수정했었다. 하지만 위의 반례에서 처럼, smaller == 0이고, 0이 사용할 수 있는 경우 누락이 발생하게 된다. 따라서, CONTINUE_S 플래그 아래에 smaller == 0이면서 0이 사용할 수 없을 때에만 smaller에 -INF를 대입하도록 했다. 그리고 제출을 했더니... 맞았습니다!

---

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define INF 987654321
#define EL "\n"

int digit(int n) {
	if (n == 0)
		return 1;
	int d = 0;
	for (int i = n; i > 0; i /= 10)
		d++;
	return d;
}

int main() {
	FAST_IO;

	int N;
	int M;
	cin >> N >> M;

	char brokenButtons[10];
	for (int i = 0; i < M; i++)
		cin >> brokenButtons[i];

	// 1. All numbers is broken
	bool isAllBroken = true;
	for (int i = 0; i <= 9; i++) {
		bool isFound = false;
		for (int j = 0; j < M; j++)
			if ('0' + i == brokenButtons[j]) {
				isFound = true;
				break;
			}
		if (isFound == false) {
			isAllBroken = false;
			break;
		}
	}
	if (isAllBroken) {
		cout << abs(N - 100) << EL;
		return 0;
	}

	// 2. N == 0
	if (N == 0) {
		for (int i = 0; i <= 9; i++) {
			bool isFound = false;
			for (int j = 0; j < M; j++)
				if ('0' + i == brokenButtons[j]) {
					isFound = true;
					break;
				}
			if (isFound == false) {
				cout << i + 1 << EL;
				return 0;
			}
		}
	}

	// 3. Only 0 is available.
	bool isOnlyZero = true;
	for (int i = 1; i <= 9; i++) {
		bool isFound = false;
		for (int j = 0; j < M; j++)
			if ('0' + i == brokenButtons[j]) {
				isFound = true;
				break;
			}
		if (isFound == false) {
			isOnlyZero = false;
			break;
		}
	}
	if (isOnlyZero) {
		if (N < 50)
			cout << 1 + N << EL;
		else
			cout << abs(N - 100) << EL;
		return 0;
	}

	// 4. General
	// 4-1. A Smallest number of numbers greater than N.
	int greater = N;
	while (true) {
		for (int i = greater; i > 0; i /= 10) {
			for (int j = 0; j < M; j++) {
				if ('0' + i % 10 == brokenButtons[j]) {
					greater++;
					goto CONTINUE_G;
				}
			}
		}
		break;
	CONTINUE_G:;
	}
	// 4-2. A Greatest number of numbers smaller than N.
	int smaller = N;
	while (true) {
		for (int i = smaller; i > 0; i /= 10) {
			for (int j = 0; j < M; j++) {
				if ('0' + i % 10 == brokenButtons[j]) {
					smaller--;
					goto CONTINUE_S;
				}
			}
		}
		break;
	CONTINUE_S:
		if (smaller == 0) {
			int isZeroUnavailable = false;
			for (int i = 0; i < M; i++)
				if (brokenButtons[i] == '0')
					isZeroUnavailable = true;
			if (isZeroUnavailable) {
				smaller = -INF;
				break;
			}
		}
	}
	// 4-3. Get minimum and print
	int result = min(min(greater - N + digit(greater), N - smaller + digit(smaller)), abs(N - 100));
	cout << result << EL;

	return 0;
}

ps. 다른 정답자 코드를 보면 0부터 적당한 수까지 매 번 버튼을 누르는 횟수를 세며 최솟값을 찾는 노가다를 했다. 사실 이 문제의 의도가 그런거다. 이 풀이에서 볼 수 있다시피, 고려해야 할 요소가 많으니까.