백준 1107 리모컨 c++

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

1107번: 리모컨

진짜 토 나오는 반례가 많다.. 도저히 못 찾겠어서 질문글에 반례 100개 넘게 치고 다 고쳐서 통과했다.

대충 큰 문제가 0이 고장 났는데 dfs는 0부터 시작해서 생기는 문제 -> valid 한 지 확인하고 dfs 돌았다.

target이 이미 100이라서 -+만 눌러도 될 경우 -> 숫자채널변경 없이 +-만 사용해서 target 가는 cnt 세서  둘 중 작은 값으로 제출했다.

target이 8일 때 10에서 갈 때, 6에서 갈 때 cnt 더 작은 6에서 가야 함 -> dfs 조건에서 channel length도 비교해 주었다.

 

그냥 토악질 나온다. 이거 한 번에 통과하는 사람 그냥 폰 노이만임;

#include <string>
#include <vector>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stack>
#include <unordered_set>
#include <utility>
#include <cmath>
#include <cstring>
using namespace std;
 // 9:20pm ~ 10: 51 tlqkf 반례만 한시간동안 찾음
bool isValid[10];
int target, wrongCnt, channel = 100;

int getLength(int num) {
	int i = 0;
	if (num == 0)
		return 1;
	while (num) {
		num /= 10;
		i++;
	}
	return i;
}

void dfs(int num) {
	if (abs(num - target) < abs(channel - target))
		channel = num;
	else if (abs(num - target) == abs(channel - target) && getLength(num) < getLength(channel))
		channel = num;
	for (int i = 0; i <= 9; i++) {
		if (isValid[i]) {
			int cur = num * 10 + i;
			if (abs(num - target) > abs(cur - target))
				dfs(cur);
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(isValid, 1, sizeof(isValid));
	cin >> target >> wrongCnt;
	for (int i = 0; i < wrongCnt; i++) {
		int input;
		cin >> input;
		isValid[input] = false;
	}
	int noChangeChannelCnt = abs(target - channel);
	for (int i = 0; i <= 9; i++)
		if (isValid[i])
			dfs(i);
	// cout << "channel: " << channel <<endl;
	int res = getLength(channel) + abs(target - channel);
	cout << min(res, noChangeChannelCnt);
}