[백준] 1107 리모컨

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

1107번: 리모컨

 

 

 

[처음 틀린 풀이방법]

<숫자버튼을 클릭하는 경우>

1. 각 자리수를 비교하면서 가장 작은 차인 원소를 선택한다.

2. 모든 자리수를 선택한 후 비교한다. 차이만큼 버튼 클릭수에 + 해준다.

 

ex) 타켓넘버 5457 이고 사용가능한 숫자버튼이 0, 1, 2, 3, 4, 5, 9 일 경우

첫째자리 5 와 가장 차이가 작은 원소인 5 선택

두번째자리까지 54 와 가장 차이가 작은 원소인 4 선택

세번째 자리까지 545와 가장 차이가 작은 원소인 5선택

네번째 자리까지 5457과 가장 차이가 작은 원소인 5 or 9 선택

5455 와 5457의 차이인 2를 더함.

 

<+,- 버튼만 사용하는 경우>

1. 타켓 숫자와 100 의 차이를 구한다.

 

위 두 경우에서 최소값을 답으로 리턴한다.

 

문제가 되는 이유는!

예제케이스는 다 맞는데, 

만약,

1555

8

0 1 3 4 5 6 7 9

를 위의 방식대로 한다면

2888을 버튼으로 입력하게 되는데...

해보면 알 수 있듯이 888을 입력했을 경우가 최소이다.

 

따라서, 모든 경우를 그냥 눌러보자! 가 포인트이다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int target;
int err;
bool button[10];
int min_answer = 987654321;

// 버튼 누르기
void solve(int target) {

	string str_target = to_string(target);

	int choice = 0;
	int click = 0;

	for(int i=1; i<=str_target.size(); i++) {
		int target_tmp = stoi(str_target.substr(0, i));

		int diff = 987654321;
		int n_botton = -1;
		for(int i=0; i<10; i++) {
			if(button[i] == false) continue;
			if(diff > abs(target_tmp - ((choice*10) +i))) {
				n_botton = i;
				diff =  abs(target_tmp - ((choice*10) +i));
			}
		}
		if(n_botton != -1) {
			click++;
			choice = choice * 10 + n_botton;
		}
		else
			return;
	}

	int diff = abs(target - choice);

	min_answer = min(click+diff, min_answer);

}


int main() {
	scanf("%d", &target);

	min_answer = min(abs(target-100), min_answer);

	scanf("%d", &err);

	memset(button, true, sizeof(button));

	for(int i=0; i<err; i++) {
		int tmp;
		scanf("%d", &tmp);
		button[tmp] = false;
	}

	solve(target);

	printf("%d\n", min_answer);


}

 

[옳은 풀이방법]

1. 번호를 하나씩 눌러보자

2. 누를때마다 얼마나 타겟넘버와 차이가 나는지 확인을 해서 필요한 클릭수를 계속 업데이트 시켜준다.

3. 타겟번호의 최대값은 500,000 임으로 6자리 이상일 경우 재귀를 종료한다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int target;
int err;
bool button[10];
int min_answer = 987654321;


void find(string no) {
	for(int i=0; i<10; i++) {
		if(button[i] == false) continue;
		string tmp_no = no + to_string(i);

		int tmp_click = abs(target-stoi(tmp_no)) + tmp_no.size();
		min_answer = min(min_answer, tmp_click);

		if(tmp_no.size() < 6)
			find(tmp_no);
	}
}


int main() {
	scanf("%d", &target);

	scanf("%d", &err);

	memset(button, true, sizeof(button));

	for(int i=0; i<err; i++) {
		int tmp;
		scanf("%d", &tmp);
		button[tmp] = false;
	}

	min_answer = min(abs(target-100), min_answer);

	find("");

	printf("%d\n", min_answer);


}