[백준 1107] 리모컨

문제설명

이 문제는 이동할 채널, 고장난 버튼을 입력 받고 채널 100번에서 최소한으로 이동하여 목표 채널에 도달하는 것이다

최소 이동 수를 출력시킨다

알고리즘

1. 입력이 불가능한 숫자 버튼을 배열에 true로 집어 넣는다 (arr[0]~arr[9]까지 중, true이면 그 버튼은 누를 수 없음)

2. N의 값이 100이면 바로 0을 출력 시킨다(버튼을 누를 필요 없음)

3. M의 값이 0이거나 현재 이동하려는 채널의 모든 버튼이 고장 나지 않은 경우 비교가 필요하다->(100번에서 + 또는 -를 이용해 가는데 필요 한 횟수, 숫자의 자리수)  => 더 작은 값 출력

4. 가려는 채널의 버튼이 고장난 경우 반복문을 통해서 계산한다

    4.1) minus, plus 선언 후, 해당 값이 리모컨으로 만들 수 있는 경우, 이동값(count) + 현재 만든 숫자의 자리수가 답이 된      다

    4.2) 4.1에서 계산한 값보다 100에서 +,-로 이동한 값(count100)이 더 작은 경우가 발생하기 때문에 이때는 count100을 출력한다

 

코드

#include<iostream>
#include<string>
using namespace std;
bool arr[10];
string input;

bool mal_check(int x) { //현재 값이 리모컨으로 만들 수 있는지 확인
	string temp = to_string(x);
	for (int i = 0; i < temp.length(); i++)
	{
		if (arr[temp[i] - '0'])//고장난 곳 누름
			return false;
	}
	return true;//전부 누를 수 있음
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int x; 
		cin >> x;
		arr[x] = true;//고장난 버튼 체크 
	}
	
	int count100 = abs(N - 100); //100에서 +,-로 이동하는데 걸리는 값
	input = to_string(N);
	if (N== 100) //이동할 필요 없음 -> 현재 100번 채널 이므로
	{
		cout << 0;
		return 0; 
	}
	
	if (mal_check(N) || M==0) { //현재 바로 눌러도 되는 경우 (잘못된 버튼이 없거나 있어도, 피해갈 수 있는 경우)
		
		if (count100 >= input.length())//직접 숫자를 누르는게 빠른 경우
			cout << input.length();
		else//100에서 +,-로 이동하는게 더 빠른경우 
			cout << count100;

		return 0;
	}

	int minus = N, plus = N;
	int count = 0;

	while (1) {

		minus -= 1;
		plus += 1;
		count++;//이동 횟수 

		if (count + to_string(minus).length()> count100) {//100에서 +,-로 이동하는게 더 빠른 경우
			cout << count100;
			return 0;
		}

		if (mal_check(minus) && minus>=0 ) {//-1씩 내려봤는데, 그 값으로 이동하는게 최적화인경우
			cout << count + to_string(minus).length();
			return 0;
		}

		if (mal_check(plus)) {//+1씩 올렸는데, 그 값이 최적화 인경우
			cout << count + to_string(plus).length();
			return 0;
		}
	}

}

고찰

이 문제는 반례가 너무 많은 문제여서 꽤 고생을 했다 

푸는중 가장 도움 되었던 링크이다

https://www.acmicpc.net/board/view/46120

글 읽기 - [반례모음]

헷갈리는 테스트 케이스가 전부있어서 해결할 수 있었다

---

생각하지 못했던 케이스는, 바로 리모컨으로 숫자를 누를 수 있는데, 그게 100에서 +,-로 이동할 수 있는 경우가 더 최솟값 인 케이스였다 .

예를들어, 

101, 3, {4,5,6} 이 입력인 경우 답은 리모컨으로 직접 누른 3이 아닌 +를 누른 1이었다