[백준][C++] 1107: 리모컨

문제 링크: https://www.acmicpc.net/problem/1107

 

완전탐색 문제입니다.

숫자 버튼으로 만들 수 있는 채널의 조합을 만들어서 목표 채널까지 도달할 때 버튼을 누른 횟수중 최소를 구하면 됩니다. 현재 채널이 100이라는 점도 감안해야 합니다.

그리고 채널 조합을 만들 때 한자리 위아래의 값도 들어가야 합니다.

 

예를 들어

//입력
9
8
0 3 4 5 6 7 8 9

//출력
4

위 예시의 경우, 11을 누르고 -를 두번 누르면 4번만에 채널 9에 갈 수 있겠죠.

 

//입력
1555
8
0 1 3 4 5 6 7 9

//출력
670

이 예시에서는 888을 누르고 -를 667번 누르면 1555번에 갈 수 있습니다.

 

반례가 은근 많습니다 ㅠㅠ 설계부터 완벽하게 하고 짜야 반례지옥에서 벗어날 수 있습니다..

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

const int INF = 987654321;

string s;
int n, m, len;
bool not_working[10];	//고장=true


int solve(int idx, int input, int max_len) {
	int ret = INF;

	if (idx != 0)
		ret = abs(input - n) + idx;

	if (idx == max_len)
		return ret;

	for (int i = 0; i < 10; ++i) {
		if (!not_working[i]) {
			ret = min(ret, solve(idx + 1, input + i * pow(10, idx), max_len));
		}
	}

	return ret;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	s = to_string(n);
	int tmp;
	for (int i = 0; i < m; ++i) {
		cin >> tmp;
		not_working[tmp] = true;
	}
	len = s.size();

	cout << min({ solve(0, 0, len), solve(0, 0, len+1), abs(100 - n) });

	return 0;
}

위 코드는 잘 동작은 하는데 지금 보니 채널을 0부터 누르고 시작할 때 쓸데없는 계산을 하는 경우가 있겠네요.

이 문제에 헛심을 너무 많이 썼기 때문에.. 수정은 나중에 생각나면 하겠습니다.