글 읽기 - 반례를 못찾겠습니다...뭐가 문제인지 도움이 필요합니다.

oursoon2 7년 전 0

문제에 나와 있는 경우와 질문에 예상되는 반례들 다 대입해보았는데, 모두 정답인거 같은데

왜 틀렸다고 하는지 모르겠네요....

이걸로 몇시간째 고민중인데, 생각의 한계를 못벗어나네요.

반례좀 구해주세요ㅠ

#include <stdio.h>

bool button[10];

bool is_possible(int channel) {
	if (channel == 0) {
		if (button[0]) {
			return true;
		}
		else {
			return false;
		}
	}
	while (channel > 0) {
		if (button[channel % 10] == true) {
			channel /= 10;
		}
		else {
			return false;
		}
	}
	return true;
}

int get_button_count(int channel) {
	int count = 0;
	if (channel == 0) {
		return 1;
	}
	while (channel > 0) {
		channel /= 10;
		count++;
	}
	return count;
}

int main()
{
	int N = 0;
	int broken_count = 0;
	int broken_num = 0;
	int i = 0;
	int loop_count = 0;
	int count = 0;
	int pm = 0;
		
	for (i = 0; i < 10; i++) {
		button[i] = true;
	}

	scanf("%d", &N);
	scanf("%d", &broken_count);

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

	if (N - 100 < 0) {
		loop_count = -1 * (N - 100);
	}
	else {
		loop_count = N - 100;
	}
	
	
	for (i = 0; i <= 1000000; i++) {
		if (is_possible(N - i)) {
			count = i + get_button_count(N - i);
			break;
		}
		else if(is_possible(N + i)) {
			count = i + get_button_count(N + i);
			break;
		}
	}

	if (loop_count > count) {
		loop_count = count;
	}

	printf("%d", loop_count);
		
	return 0;
}

evenharder 7년 전 0

0 1 2 3 4 5 6 7 8 9

를 입력으로 집어넣으면 답은 100일텐데(-를 100번 눌러야 하니까요) 프로그램은 1을 출력합니다.

fresmic 7년 전 1

입력이

0 1 2 3 4 5 6 7 8

일때, 1이 출력되네요.

is_possible(int) 함수가 음수에 대해 true값을 반환하여 생기는 문제같네요~ :D

oursoon2 7년 전 0

fresmic님 말처럼 채널이 음수가 될 경우를 생각안해서 생긴 문제네요...

완전 탐색에서 제가 생각하지 못한 예외 케이스까지 다 찾을 수 있는 노하우같은게 있으신 분 조언 부탁드립니다.

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

문제

문제

출처

ICPC

반례를 못찾겠습니다...뭐가 문제인지 도움이 필요합니다.

oursoon2 7년 전 0

evenharder 7년 전 0

fresmic 7년 전 1

oursoon2 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말