백준 1107 [C++]

www.acmicpc.net/problem/1107

1107번: 리모컨

1. 풀이방법

 

- 개인적으로 참 어려웠던 문제였습니다...

 

- 처음에는 경우의 수를 나눠서 1번 (+,-만으로만 접근) 2번 (버튼만으로 접근이 가능한 경우) 3번 (버튼으로 근접하게 간 후 +,- 로 이동해야하는 경우) 3가지 중 min 값을 출력하자 라고 했습니다.

 

- 하지만 저 3번....! 저걸 찾아내는게 굉장히 까다로웠습니다. 숫자를 하나씩 맞춰본다거나, 

  고장난 버튼이면 최대한 근접한 버튼을 누르는데 위,아래 어느 숫자쪽으로 탐색을 해야하나....

 

- 하나의 아이디어를 준 것은 바로 +,-는 마지막에 눌러진다는 것입니다. +,- 버튼을 누르고 나서 숫자를 누를경우 

  처음 부터 다시 숫자를 매겨야 하죠 (보통의 리모컨을 생각해 보시면 될 것 같습니다.)

 

- 그래서 생각해낸 것은 바로.....!

 

- 1. 일단 -1로 모든번호를 저장할 테이블들을 모두 초기화 ! (위로 갔다가 -로 돌아오는 경우도 있으므로 백만까지)

 

- 2. 버튼으로 이동할 수 있는 번호의 경우 테이블에 미리 다 몇번의 버튼을 눌러서 갈 수 있는지 저장!!!!

 

- 3. 찾고자 하는 채널이 -1, 즉 버튼만으로 갈 수 없는 경우 위,아래로 탐색해서 가장 가까이 있는 버튼으로 갈 수 있는

      번호를 찾는다 !!!!!!

( 물론 상기의 과정 중 +,- 버튼만으로 가는 것이 더 적은 수로 이동할 수 있는 경우 그 숫자를 넣어줘야 합니다.)

 

 

 

 

2. 주의사항

 

- 리모콘은 고장나면 쫌 사자.....

 

 

 

 

3. 나의코드

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

int N,M;
int remote[10]; //0~9
int casestore[1000001];
int len;

bool onlynum(int num) {
	len = 0;
	int tmp = num;
	while (1) {
		if (remote[tmp % 10] == true) return false; //고장나서 버튼만으로는 이동불가
		tmp /= 10;
		len++;
		if (tmp == 0) break;
	}
	return true;
}
void inputs() {
	cin >> N >> M;
	int tmp;
	for (int i = 0; i < M; i++) {
		cin >> tmp;
		remote[tmp] = true; //true는 고장
	}
}
void makecase() {
	casestore[100] = 0;
	for (int i = 0; i < 1000001; i++) {
		if (i == 100) continue;
		if(onlynum(i)==true)
		{
			casestore[i] = min(abs(i - 100), len);
		}
	}
}
void setcase() {
	for (int i = 0; i < 1000001; i++) {
		casestore[i] = -1;
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	setcase();
	makecase();

	if (N == 100) { cout << 0 << "\n"; return 0; }
	if(casestore[N]!=-1){
		cout << casestore[N] << "\n"; return 0;
	}
	else{
		int index = 1;
		while (1) {
			if (N - index >= 0) {
				if (casestore[N - index] != -1) {
					cout << min(abs(N - 100),casestore[N - index] + index) << "\n";
					return 0;
				}
			}
			if (N + index <= 1000000) {
				if (casestore[N + index] != -1) {
					cout << min(abs(N - 100),casestore[N + index] + index) << "\n";
					return 0;
				}
			}
			index++;
		}
	}
	return 0;
}