글 읽기 - (BFS)리모콘 문제... 반례좀 찾아주실 수 있을까요ㅜㅜ

ivorymood 3년 전 0

게시판 반례로 안되네요..

//https://www.acmicpc.net/problem/1107
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int N;
int nearest = 100;
int cnt;

void perm(const string &numbers, string output, int depth, int r)
{
	if (depth == r)
	{
		int res = stoi(output);
		// 버튼 누른 총 횟수 : 가장 가까운 채널 길이 + (+/-) 버튼 누른 횟수
		if(abs(nearest - N) > abs(res - N) + to_string(res).size())
		{
			nearest = res;
			cnt = abs(res - N) + to_string(res).size();
		}
		return ;
	}

	for (int i = 0; i < numbers.size(); i++)
	{
		perm(numbers, output + numbers[i], depth + 1, r);
	}
}

int broken_cnt(int N, bool is_broken[]) // 수정
{
	int cnt = 0;
	do
	{
		if (is_broken[N % 10])
		{
			cnt++;
		}
		N /= 10;
	} while (N);
	return cnt;
}

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

	const int now = 100;

	// 입력
	int M;
	cin >> N >> M;
	bool is_broken[10] = { 0, };
	
	for (int i = 0; i < M; i++)
	{
		int tmp;
		cin >> tmp;
		is_broken[tmp] = true;
	}

	// 목표 채널이 현재 채널이거나, 모든 숫자버튼이 고장났을 때
	if (abs(N - now) == 0 || M == 10)
	{
		cout << abs(N - now);
		return 0;
	}
	// 만들려는 채널 숫자에 해당하는 고장난 버튼이 없을때
	if (broken_cnt(N, is_broken) == 0)
	{
		cout << to_string(N).size();
		return 0;
	}

	// 정상 버튼 문자열 만들기
	string numbers;
	for (int i = 0; i < 10; i++)
	{
		if (!is_broken[i])
		{
			numbers.push_back((char)i + '0');
		}
	}

	// 정상버튼으로 목표채널과 가장 가까운 채널 만들기
	perm(numbers, "", 0, to_string(N).size());

	// 버튼을 가작 적게누르는 가장 가까운 채널이 현재 채널이면
	if (nearest == now)
	{
		cnt = abs(N - now);
	}
	
	cout << cnt;

	return 0;
}

swdaniel 3년 전 4

9999

답: 6 (10000-)

출력: 1118

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(BFS)리모콘 문제... 반례좀 찾아주실 수 있을까요ㅜㅜ

ivorymood 3년 전 0

swdaniel 3년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말