[알고리즘] 백준 1107번: 리모컨 (C++), 모든 경우의 수

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

1107번: 리모컨

이번 문제는 어떠한 논리라기보다 너무 복잡한 생각을 필요하지 않은 문제다.

오히려 간단해지기 위해 복잡한 생각을 해야 했던 문제(?)였다.

 

처음에는 어떻게 최솟값을 도출할지를 생각하는 과정에서 두 가지로 나뉘었다.

1. 한 번에 최솟값을 도출하는 방법(?)
2. 모든 채널을 대입해보면서 최솟값을 찾는 방법

1번 방법은 생각만 해도 반례가 너무 많을 거 같았다. 주어진 수가 500,000이라면 5 버튼이 고장 났을 때, 499,999를 어떻게 도출해낼지 감이 오지 않았다.

2번 방법은 최후의 수단으로 남겨뒀지만 도저히 방법이 떠오르지 않아서 2번으로 택했다.

>> 문제를 읽었을 때는 엄청 복잡한 문제라고 생각했지만 구현하면서 차근차근 절차를 밟다 보니 엄청 복잡한 문제는 아니구나라는 생각이 들었다.

 

---

솔루션

2번 방법도 2가지 경우로 나뉜다.

 

[연산자만 사용해서 채널에 도달하는 경우 vs 근접한 숫자를 입력 후, 연산자 사용]

무엇이 더 최솟값을 유발하는지는 수마다 다르고, 고장 난 숫자도 경우에 따라 달라지기 때문에 둘 다 구해서 둘 중 무엇이 더 작은지 알아내야 한다.

cout << min(onlyUseOperator(), closeTheNumber());

 

[연산자만 사용해서 채널에 도달하는 경우]

시작 채널 값이 100이기 때문에 1000이라면 900번 정도 +를 눌러주고, 10이라면 90번 -를 눌러준다.

>> (입력 값 - 100)의 절댓값을 구해주면 된다.

int onlyUseOperator() { // 연산자만 사용해서 이동하는 방법
	return abs(n - 100);
}

 

[근접한 숫자를 입력 후, 연산자 사용]

이 부분에서 이 문제는 브루트 포스라고 할 수 있다.

모든 경우를 다 따져야 최솟값을 구할 수 있기 때문이다.

int closeTheNumber() { // 숫자로 근접해서 +,- 사용
	int result = INT_MAX;
	for (int i = 0; i <= 1000000; i++) {
		if (check(i)) {
			int temp = abs(n - i) + to_string(i).length();
			result = min(temp, result);
		}
	}
	return result;
}

1) 범위가 1,000,000인 이유는?

왜 다른 큰 수도 아니고 1,000,000인지는 이유를 내놓을 수 없다. 그런 경우를 생각했다. 500,000을 구하는데

이렇게 고장 나는 경우를 생각해봤다.

0
0 1
0 1 2
0 1 2 3
0 1 2 3 4 
0 1 2 3 4 5
0 1 2 3 4 5 6
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8 9

포인트)

0~5까지 고장 나면 666666에서 내려가야 하고, 0~8까지 고장 나면 999999에서 내려가야 하기 때문에 1000000을 범위로 설정했다.

 

2) check() 함수의 의미는?

i에 주어진 수로 모든 경우를 다 따질 수는 없다. 고장 난 숫자 버튼이 있기 때문에 check함수에서 이 숫자가 리모컨에서 나올 수 있는 숫자인지 판단을 한다.

bool check(int value) {
	string s = to_string(value);
	for (int i = 0; i < s.size(); i++) {
		if (broken[s[i] - '0']) {
			return 0;
		}
	}
	return 1;
}

>> 문자열로 변환해서 사용

 

---

[AC 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
using namespace std;

vector<bool> broken(10, false); // 고장난 버튼 넣을 배열
int n;

bool check(int value) {
	string s = to_string(value);
	for (int i = 0; i < s.size(); i++) {
		if (broken[s[i] - '0']) {
			return 0;
		}
	}
	return 1;
}

int onlyUseOperator() { // 연산자만 사용해서 이동하는 방법
	return abs(n - 100);
}

int closeTheNumber() { // 숫자로 근접해서 +,- 사용
	int result = INT_MAX;
	for (int i = 0; i <= 1000000; i++) {
		if (check(i)) {
			int temp = abs(n - i) + to_string(i).length();
			result = min(temp, result);
		}
	}
	return result;
}

int main() {
	int m;
	cin >> n >> m;
	int num;
	for (int i = 0; i < m; i++) {
		cin >> num;
		broken[num] = 1;
	}

	cout << min(onlyUseOperator(), closeTheNumber());
	return 0;
}

---

문제 자체에 접근하기는 다른 문제보다 꽤 부담스러운 문제였다. 차근차근 경우와 절차를 나누고 단계별로 해결해나가다 보면 풀리는 구현 문제이자 브루트 포스 문제였다.

업 솔빙 무조건 해야 하는 문제