반례(counterexample)를 자동으로 찾아 주는 코드(Python/C)

가끔 문제를 풀다 보면 예제도 다 통과했는데 도대체 왜 틀렸는지 알 수 없는 문제들이 있다. (왜맞틀?????) 그럴 때 진짜 답답해서 미쳐버릴 거 같은 심정으로 반례를 찾아 헤매는데 이게 찾기 쉽지 않다. 그럴 때는 반례 생성기를 만들어서 찾으면 된다.

 

이 반례 생성기는 백준 1654문제를 기준으로 만들었다. 

총 3단계에 걸쳐서 작성을 한다.

 

Python

1. 예제 생성 함수 작성( EX.입력값)

우선 example()이라는 예제 생성 함수를 만든 뒤, 문제에 맞춰서 randint()으로 최소 값, 최대 값 주고 예제를 생성하면 된다.

원래 1<=K<=10,000, 1<=N<=1,000,000, 랜선의 길이는 <=2,147,483,647인데 그렇게 하면 변수 값이 너무 커지니 임의로

줄였다. 

def example():
	K = randint(1, 10)
	N = randint(K, 20) # K <= N
	lines = [0] * K

	for i in range(K):
		lines[i] = randint(1, 1000)
	return [K, N, lines]

2. 맞는 답 & 틀린 답을 실행하는 함수 작성!

맞는 답은 인터넷에서 정답 코드를 구하여 복붙을 하면 되고

틀린 답은 자신이 작성한 틀린 코드를 복붙하면 된다. 

def right_sol(K, N, lines):
	s = 1
	e = max(lines)

	res = 0
	while s <= e:
		cnt = 0
		m = (s+e)//2
		for i in lines:
			if i >= m:
				cnt += i // m
		if cnt < N:
			e = m - 1
		else:
			res = m
			s = m + 1
	return res

def wrong_sol(K, N, lines):
	s = 0
	e = max(lines)

	res = 0
	while s <= e:
		cnt = 0
		m = (s+e)//2
		for i in lines:
			if i > m:
				cnt += i // m
		if cnt < N:
			e = m - 1
		else:
			res = m
			s = m + 1
	return res

 

3. 반례 출력 함수 작성

이제 반례 출력하는 함수를 만들면 끝이다. ex라는 변수에다가 예제 생성 함수의 리턴 값을 담고, 그 예제로 맞은 코드와 틀린 코드를 실행하면 된다. 만약 둘의 리턴 값이 같을 경우 다시 실행하고, 아니면 반례를 출력하게 했다. 

def check():
	ex = example()
	right = right_sol(ex[0], ex[1], ex[2])
	wrong = wrong_sol(ex[0], ex[1], ex[2])
	if right != wrong:
		print(ex[0], ex[1])
		for i in ex[2]:
			print(i)
		print("맞은 답:", right)
		print("틀린 답:", wrong)
		return
	else:
		check()

 

전체 코드

from random import randint

# 예제 생성
def example():
	K = randint(1, 10)
	N = randint(K, 20)
	lines = [0] * K

	for i in range(K):
		lines[i] = randint(1, 1000)
	return [K, N, lines]

# 맞은 답
def right_sol(K, N, lines):
	s = 1
	e = max(lines)

	res = 0
	while s <= e:
		cnt = 0
		m = (s+e)//2
		for i in lines:
			if i >= m:
				cnt += i // m
		if cnt < N:
			e = m - 1
		else:
			res = m
			s = m + 1
	return res

# 틀린 답
def wrong_sol(K, N, lines):
	s = 0
	e = max(lines)

	res = 0
	while s <= e:
		cnt = 0
		m = (s+e)//2
		for i in lines:
			if i > m:
				cnt += i // m
		if cnt < N:
			e = m - 1
		else:
			res = m
			s = m + 1
	return res

# 반례 출력
def check():
	ex = example()
	right = right_sol(ex[0], ex[1], ex[2])
	wrong = wrong_sol(ex[0], ex[1], ex[2])
	if right != wrong:
		print(ex[0], ex[1])
		for i in ex[2]:
			print(i)
		print("맞은 답:", right)
		print("틀린 답:", wrong)
		return
	else:
		check()

check()

 

C

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

int	K, N;

void	example(void)
{
	K = rand() % 100;
	N = rand() % 100;
}

int	incorrect(int K, int N, int lines[])
{
	int	start, end, res, mid;
	start = 1;
	end = 1;

	while (1)
	{
		res = 0;
		mid = (start + end) / 2;
		for(int i = 0; i < K; i++)
		{
			res += (lines[i] / mid);
		}
		if (res < N)
			end = mid - 1;
		else
			break ;
	}
	return (0);
}

int	correct(int K, int N, int lines[])
{
	int res;
	int max;
	long long int start = 1;
	long long int end = 1;
	long long int mid = 1;

    while (1)
	{
		res = 0;
		mid = (long long int)((start + end) / 2);

		for(int i = 0; i < K; i++)
		{
			res += (lines[i] / mid);
		}

		if (res < N)
			end = mid - 1;
		else
		{
			max = mid;
			start = mid + 1;
		}

		if (start > end)
			break ;
	}
	return (max);
}

int	main(void)
{
	int	right;
	int	wrong;

	example();
	int lines[K];

	for(int i = 0; i < K; i++)
	{
		lines[i] = rand() % 100;
	}
	right = correct(K, N, lines);
	wrong = incorrect(K, N, lines);
	while (right == wrong)
		main();
	printf("예제: K = %d, N = %d\n", K, N);
	printf("lines: ");
	for(int i = 0; i < K; i++)
	{
		printf("%d ", lines[i]);
	}
	printf("\n");
	printf("맞은 답: %d\n", right);
	printf("틀린 답: %d\n", wrong);
	return (0);
}

엄청 어려운 것도 아닌데 왜 지금까지 이런 걸 만들 생각을 못했는지 모르겠다. 허허... 이제 만들어 놨으니 요긴하게 써먹어야지!