BOJ(C++) / 백준 1107 : 리모컨

백준 1107 : 리모컨

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

1107번: 리모컨

 

문제

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

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

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

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

 

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

 

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

 

코드

//백준 1107 리모컨
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int button[10] = { 0, };

//고장난 버튼을 눌렀는지 판단
bool button_check(string num) {
	for (int i = 0; i < num.size(); i++) {
		if (button[num[i] - '0'] == 1)
			return false;
	}
	return true;
}

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

	string N;
	int M;
	cin >> N;
	cin >> M;
	for (int i = 0; i < M; i++) {
		int num;
		cin >> num;
		button[num] = 1;
	}

	if (N == "100") {
		cout << "0" << "\n";
		return 0;
	}

	int count_100 = max(100, stoi(N)) - min(100, stoi(N)); //100번에서 +, -

	int count = 0;
	string num_up = N;
	string num_down = N;
	while (1) {
		//100번에서 +-한것보다 클 때
		if (count + num_down.size() > count_100) {
			count = count_100;
			break;
		}
		//
		if (button_check(num_down) == true && stoi(num_down) >= 0) {
			count += num_down.size();
			break;
		}
		else if (button_check(num_up) == true) {
			count += num_up.size();
			break;
		}
		num_up = to_string(stoi(num_up) + 1); // +1
		num_down = to_string(stoi(num_down) - 1); /// -1
		count++;
	}
	cout << count << "\n";



	return 0;
}

 

설명

 

브루트 포스(brute force) 문제이다. 브루트 포스 알고리즘은 무식하게 전체를 탐색하는 알고리즘이다.

이번 문제도 전체를 탐색하여 구현할 수 있었다.

• 100번에서 +, - 만으로 몇 번을 눌러야 하는지 count_100 변수에 저장한다.
• 반복문으로 이동하려는 채널 N에서 + 혹은 -을 몇번 눌러 고장나지 않은 버튼으로 이동할 수 있는지 count한다.
• 고장나지 않은 버튼의 채널로 이동하여 count를 더 해준 값을 출력한다.
• 이때 count_100의 값보다 크다면 count_100을 출력한다.  

고찰

걸린시간 : 1시간 반

처음에는 DP문제인가 고민했다. 하지만 브루트포스 문제였고 진짜 이걸 반복문으로 전체를 다 돌면서 구해야되나? 의문스러웠지만 결국 전체를 다 도는것이 맞았다. 생각보다 시간이 오래 걸렸다. 생각하지 못한 예외 케이스도 많았어서 엄청 많이 틀리고 결국 맞았다. 예외케이스를 테스트 안해봤으면 맞기 힘들었을거 같다.

시간이 여유롭다면 전체 탐색하는 알고리즘인 브루트포스를 이용하여 푸는 방법도 고려를 해봐야 한다. 

 

난이도

Gold 5