개요

백준1107(리모컨)

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

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

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

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

접근 방식

1. 처음 시도는 굉장히 복잡한 방식이였다.
   타겟 번호에서 제일 가까운 수를 찾아내는 방식을 사용했다.
   타겟 번호를 네 가지로 나눴다.

   1. 타겟 번호에 고장난 숫자가 포함되었을 때 고장난 숫자 자리에,
   • 고장난 숫자보다 큰 수 중 가장 가까운 숫자를 대입한 후, 나머지 숫자를 고장난 숫자를 제외하고 제일 작은 수로 채워넣기.
   • 고장난 숫자보다 작은 수 중 가장 가까운 숫자를 대입한 후, 나머지 숫자를 고장난 숫자 제외하고 나머지 수 중 제일 큰 수로 채워넣기.
   2. 타겟 번호보다 한 자리 더 큰 수 중 제일 작은 수 ( 고장난 숫자 제외) ex) 100 -> 1000
   3. 타겟 번호보다 한 자리 더 작은 수 중 제일 큰 수( 고장난 숫자 제외) ex) 100->99

2. 문제는 위와 같은 방식으로 하면 반례가 생긴다.
   자릿수가 같으면서 고장난 숫자 이전의 자릿수 숫자가 더 큰 경우가 답인 경우가 있다.
   이런 경우를 못잡아낸다.

3. 따라서 더 케이스를 추가하자니 너무 복잡해서 검색을 했다.. 너무 허탈하도록 쉬운 문제였다.
   타겟 채널 번호가 최대 50만까지밖에 없으므로 50만까지 반복문을 통해 조건에 맞는 수를 찾기만 하면 된다!

4. 고장난 숫자를 포함한 수라면 넘어간다.
   포함 안 했다면 타겟 채널과 얼마나 차이가 있는지 계산한다.
   해당 값과 100에서 up/down 버튼 계속 눌렀을 때 차이와 비교만 해주면 끝난다!

전체 코드

#include<iostream>
#include<set>
using  namespace std;
int N;
string inputStr;
int targetNum;
set<int> wrongNum;

bool CheckContainsWrongNum(int n) {
	int Mod = 0;
	if (n == 0) {
		if (wrongNum.find(0) != wrongNum.end()) {
			return true;
		}
		return false;
	}
	while (n) {
		Mod = n % 10;
		if (wrongNum.find(Mod) != wrongNum.end()) {
			return true;
		}
		n /= 10;
	}
	return false;
}

int GetDigitCnt(int n) {
	int cnt=0;
	if (n == 0) return 1;
	while (n) {
		cnt++;
		n /= 10;
	}
	return cnt;
}

int main() {
	cin >> inputStr;
	cin >> N;
	int tmpWrongNum;
	int minDiff = 500'001;
	int minDiffNum = 0;
	for (int i = 0; i < N; i++) {
		cin >> tmpWrongNum;
		wrongNum.insert(tmpWrongNum);
	}

	for (int i = 0; i < inputStr.length(); i++) {
		targetNum *= 10;
		targetNum += inputStr[i] - '0';
	}

	for (int i = 0; i < 1'000'001; i++) {
		if (CheckContainsWrongNum(i)) continue;
		if (minDiff > abs(i - targetNum)) {
			minDiff = abs(i - targetNum);
			minDiffNum = i;
		}
	}

	cout << min(minDiff + GetDigitCnt(minDiffNum), abs(targetNum - 100));
}

문풀후생

브루트 포스 문제들을 많이 안 풀어봐서 그런가 너무 복잡하게 생각하는 것 같다.
브루트 포스 문제들도 좀 풀어봐야겠다. 때론 쉽게 생각하는게 정답일지니...