글 읽기 - [C언어] 게시판의 반례를 시도해보았으나 틀려서 질문올려봅니다.

maple19out 4년 전 0

저 같은 경우 4가지 경우를 생각했습니다.

단순히 + 혹은 - 버튼을 연타하여서 채널을 이동하는 방법(option[0])
이동하려는 채널과 같은 자리수의 가능한 수 중 그 차이가 최소가 되는 방법(option[1])
이동하려는 채널보다 한 자리수 작은 가능한 수 중 그 차이가 최소가 되는 방법(option[2])
이동하려는 채널보다 한 자리수 큰 가능한 수 중 그 차이가 최소가 되는 방법(option[3])

위 4가지 경우 중에서 가장 최소인 option을 선택하는 방법으로 코드를 작성하였고 게시판의 반례들을 입력하여 올바르게 출력되었지만 여전히 틀렸다고 나옵니다. 한 번 봐주시면 감사하겠습니다.

추가적으로 이런 부르트 포스 문제 반례를 찾아주시는 분들은 어떻게 찾으시는 건지도 궁금합니다. 경우의 수가 일일이 대입해보기에는 많은데 코드의 잘못된 논리를 찾아서 반례를 찾아내시는 건가요? 아니면 이미 통과한 코드에 자동으로 경우의 수를 입력하는 프로그램같은 것을 만들어서 틀렸다고 나오는 코드와 결과값을 비교해 다른 부분의 tc를 가려내는 것인가요?

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//4가지 후보 중에서 최솟값을 찾는 함수
int best_option(int option[]){
	int i;
	int min = option[0];
	for(i=1; i<4; i++)
		if(option[i]<min)
			min = option[i];
	return min;
}

//절댓값 함수
int my_abs(int x){
	return x>0 ? x : x*-1;
}

//10 제곱 함수
int pow10(int x){
	int result=1;
	int i;

	for(i=0; i<x; i++)
		result *= 10;

	return result;
}

//정수의 길이를 판별하는 함수
int length(int x){

	int i=0;
	if(x==0)
		return 1;
	for(i=0; x!=0; i++)
		x /= 10;

	return i;
}

int main(){
	int option[4]; //후보
	int num;

	char N1[7]; //이동하려는 채널
	int length1; //채널 자리수1
	int num1; //정수꼴로 바꾸었을 때

	char N2[7]; //이동하게 되는 채널
	int length2; //채널 자리수2
	int num2; //정수꼴로 바꾸었을 때

	int M; //고장난 버튼 개수
	int broken[10]; //고장난 버튼 표기
	int button;
	int i, j, k;
	int now=100; //현재 채널
	int min=9, max=0;
	int temp;
	int temp1, temp2, temp_length;

	for(i=0; i<4; i++)
		option[i] = 0; //후보 초기화
	for(i=0; i<10; i++)
		broken[i] = 1; //버튼 상태 초기화

	scanf("%s", N1);
	getchar();
	scanf("%d", &M);
	for(i=0; i<M; i++){
		scanf("%d", &button);
		broken[button] = -1; //고장난 버튼 표기
	}
	length1 = strlen(N1);
	num1 = atoi(N1);
	for(i=0; i<10; i++){
		if(i!=0 && broken[i]!=-1 && i<min)
			min = i;
		if(broken[i]!=-1 && i>max)
			max = i;
	}

	option[0] = my_abs(num1-now); // *첫 번째 경우

	for(i=0; i<length1; i++){
		if(broken[N1[i]-'0'] == -1)
			break;
		else
			N2[i] = N1[i];
	}

	if(i!=length1){
		for(j=N1[i]-'0'+1; j<10; j++){
			if(broken[j] == 1)
			{
				N2[i] = j+'0';
				break;
			}
		}
		if(j==10)
			N2[i] = min + '0';
		for(temp = i+1; temp<length1; temp++){
			if(broken[0]==-1)
				N2[temp] = min + '0';
			else
				N2[temp] = '0';
		}
		N2[temp] = '\0';
		num2 = atoi(N2);
		temp_length = strlen(N2);
		temp1 = my_abs(num1 - num2);


		for(k=N1[i]-'0'-1; k>=0; k--){
			if(broken[k] == 1)
			{
				N2[i] = k+'0';
				break;
			}
		}
		if(k==-1)
			N2[i] = max + '0';
		for(temp = i+1; temp<length1; temp++)
			N2[temp] = max + '0';
		N2[temp] = '\0';
		num2 = atoi(N2);
		temp2 = my_abs(num1 - num2);
		length2 = strlen(N2);

		if(temp1<temp2)
			option[1] = temp1 + temp_length;
		else
			option[1] = temp2 + length2; //두 번째 옵션은 주어진 채널과 같은 자릿수의 가능한 수 중 차이가 최소가 되는 경우를 추리는 코드입니다.

		
	}

	else
		option[1] = length1;


	//세번째 경우 계산 코드. 세	번째의 경우 주어진 채널보다 한자리수 작은 채널에서 두 수의 차이가 최소가 되는 경우를 만드는 과정입니다.
	num=0;
	for(i=0; i<length1-1; i++){
		num += max;
		num *= 10;
	}
	num /= 10;
	option[2] = my_abs(num1-num) + length(num);
	if(length1==1)
		option[2] = option[0];


	//네번째 경우 계산 코드. 네 번째의 경우 주어진 채널보다 한자리수 큰 채널에서 두 수의 차이가 최소가 되는 경우를 만드는 과정입니다.
	num=0;
	num += min*pow10(length1);
	if(broken[0]!=1){
		for(i=1; i<length1-1; i++)
			num += min*pow10(length1-i);
	}

	option[3] = my_abs(num1-num) + length(num);

	if(M==10){ //버튼이 다 고장나있다면 의미없으므로 첫번째 옵션으로 모두 초기화)
		option[1] = option[0];
		option[2] = option[0];
		option[3] = option[0];
	}

	printf("%d\n", best_option(option));

	return 0;
}

seico75 4년 전 3

2229
6
4 5 6 7 8 9

위의 경우는 코드를 보고 이상한 부분을 찾고 그 경우에 걸리는 케이스를 만들었습니다.

보통은 반례를 찾을 때 말씀하신 방법을 다 사용합니다.

코너 케이스를 넣어본다. (가장 큰값, 가장 작은 값.)
로직 상 분기가 되는 모든 케이스에 대표 예 (위의 경우 각 Option 에 해당하는 케이스)
느리지만 정확한 답이 나오는 소스와 임의의 값이나 대표값들의 결과값을 비교
(남의 소스인 경우) 로직상 이상한 부분을 건드리는 예

maple19out 4년 전 1

정말 감사합니다. 제시해 주신 반례 덕분에 제 코드의 논리적 허점을 발견하였습니다. 아직 해결은 못 하였지만 보완을 해서 마무리 지을 수 있도록 하겠습니다!

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

문제

문제

출처

ICPC

[C언어] 게시판의 반례를 시도해보았으나 틀려서 질문올려봅니다.

maple19out 4년 전 0

seico75 4년 전 3

maple19out 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말