<사고력 훈련 문제 #2>: 비둘기집 원칙

# 비둘기집 원칙 문제

---

 문제) 비둘기집 원칙이란 함수 f가 n개의 상이한 입력에 대해 n개보다 작은 상이한 출력이 나온다면 $a\neq$ $b$ 이고 $f(a) = f(b)$인 두 개의 입력 a, b가 존재한다는 것이다. 이와 같이 입력값이 상이하면서 함수값이 같은 a,b를 찾는 C프로그램을 작성하라.

# 풀이

---

 이 문제는 한 가지 함수를 미리 정해두고 프로그램을 작성한다. 그 후 함수 내에 같은 y값이 나오는 x값들이 있는지 확인하는 프로그램을 작성하면 된다.

/*************************************************
 ** 비둘기집 원칙 프로그램
*************************************************/

#include <stdio.h>
#include <stdlib.h> // rand 함수를 위한 헤더
#include <time.h> // srand 함수를 위한 헤더

#define MAX 30 // 배열의 최대 크기

#define FUN(x) (x*x - 100*x + 8) // 임의의 함수 정의

// 현재 입력한 값에 따른 출력과 같은 출력을 가지는 입력의 존재여부 확인
int find(int result, int n);

int output[MAX] = { 0 }; // 각 변수의 함수결과값 저장
int inputs[MAX] = { 0 }; // 함수에서 계산된 변수 저장
// 각 배열을 0으로 초기화 해줘도 되는 이유는 위에 임의로 설정한 함수가
// 무조건 0보다 큰 값이 나올수밖에 없는 함수기 때문이다.

void main()
{
	int i, equal; // equal: 같은 함수값이 있는지 확인하는 변수
	int num, count = 0; // num: random으로 생성하는 입력값, count: 단순 카운팅 변수
	int val, result; // val: 같은 함수값을 갖는 이전 입력값

	srand((unsigned)time(NULL));
	while (count < MAX)
	{
		equal = 0;
		num = (int)((double)rand() / RAND_MAX * 100); // 0~99 난수 생성

		// 이미 사용된 입력값인지 확인한다. 우리는 같은 출력값을 가지는 다른 입력 둘을 찾고 있다.
		for (i = 0; i < count; i++)
			if (inputs[i] == num) // 기존의 입력값 배열에 내가 입력하려는 값이 있는지 확인한다.
			{
				equal = 1;
				break;
			}
		if (equal) // 같은 값이 있다면 while문의 처음으로
			continue;

		result = FUN(num); // 함수에 num을 대입한 결과값 저장

		// n개보다 작은 결과값, 즉 같은 결과값이 있다면 value를 리턴하고
		// 없다면 -1 리턴
		if ((val = find(result, count)) == -1) { // val에는 -1 또는 values[i] 값이 담긴다. (이전 입력값)
			output[count] = result; // 결과값을 배열에 저장
			inputs[count++] = num; // 변수를 배열에 저장
		}
		else {
			printf("a = %d, b = %d\n", val, num); // val: 같은 함수값을 갖는 이전 입력값, num: 현재 입력값
			break;
		}
	}
}

int find(int result, int n)
{
	int i;
	for (i = 0; i < n; i++)
		if (result == output[i])
			return inputs[i]; // 그 값을 찾은 경우 전의 입력값을 리턴한다.
	return -1; // 찾는 값이 없을 경우
}

/*************************************************
 ** End Line
*************************************************/