[C언어] 백준 1193 분수찾기

패턴을 어떻게 잡느냐에 따라 엄청 긴 코드가 나올 수도 있고 간단한 코드가 나올 수도 있음

내가 발견한 것 중 가장 간단한 접근법으로는,

n번째 대각선에 오는 분수의 개수가 n개라는 것에서 시작한다.

1/1

1/2 2/1

3/1 2/2 1/3

1/4 2/3 3/2 4/1

5/1 4/2 3/3 2/4 1/5

 

두번째 패턴으로는, n번째가 짝수일때는 1/n에서 시작해 n/1에서 끝나고, 홀수일때는 n/1에서 시작해 1/n에서 끝난다는 것이다.

따라서 N번째 분수가 몇번째 대각선에 오는지를 아는 게 문제풀이의 첫 단계가 된다.

 

#include <stdio.h>

int main(void)
{
	int num, n = 0, totN = 0;

	scanf("%d", &num);

	while (totN < num)
	{
		n++;			
		totN += n;		
	}

	// n번째 대각선의 마지막 수 번호와 num 번호의 차이: totN - num
	if (n % 2)
		printf("%d/%d", 1 + (totN - num), n - (totN - num));
	else
		printf("%d/%d", n - (totN - num), 1 + (totN - num));
	return 0;
}

n	1	2	3	4	5	6	7	8	9
totN	1	1+2	1+2+3	1+2+3+4	1+2+3+4+5	1+2+3+4+5+6	1+2+3+4+5+6+7	1+2+3+4+5+6+7+8	1+2+3+4+5+6+7+8+9
totN	1	3	6	10	15	21	28	36	45

루프가 한번 돌때마다 n과 totN의 값은 위와 같이 변해간다.

totN은 n번째 대각선의 마지막 분수가 지금까지의 모든 분수들 중 몇번째 분수인지를 나타낸다. 

 

예를 들어 num=10이라면 num은  4번째 대각선의 마지막 분수이다.

num=12라면 5번째 대각선의 (12-10)=2번째 분수이다.

 

while의 조건이 totN < num이라면,  totN이 num보다 커지거나 같아질때까지 루프를 반복하기 때문에

(마지막 루프를 돌고나서 totN은 가까스로 num과 같거나 조금 큰 값이 된다)

while문에서 벗어나는 시점의 n은 언제나 입력받은 num번째 수가 속하는 대각선 순서를 값으로 가지게 되고,

totN은 n번째 대각선에서 마지막 분수의 전체 순서(num과 같거나 큰 수)를 가지게 된다. 

 

 

변수 totN을 삭제하고 조금 더 단순화한 코드

#include <stdio.h>

int main(void)
{
	int num, n = 0;

	scanf("%d", &num);

	while (num > 0)
	{
		n++;
		num -= n;
	}

	if (n % 2)
		printf("%d/%d", 1 - num, n + num);
	else
		printf("%d/%d", n + num, 1 - num);
        
 	return 0;
 }

 

 

아래는 처음으로 풀었던 방법인데,

1부터 시작해 num까지 오기까지 모든 분수와 분모 값을 한단계씩 계속해서 조정해왔기 때문에

훨씬 비효율적이고 실제로도 시간이 엄청 걸렸다.

#include <stdio.h>

int main(void)
{
	int num, de, nu, n; //denominator:분모 numerator:분자

	scanf("%d", &num);

	de = nu = n = 1;

	while (num > 1 && (num-1)/n)				
	{

		num -= n;
		if (n % 2 == 1)
		{
			de++;
			if ((num-1) / n)
			{
				nu = de;
				de = 1;
			}
			else
			{
				nu += (num - 1);
				de -= (num - 1);
			}
		}
		else
		{
			nu++;
			if ((num-1) / n)
			{
				de = nu;
				nu = 1;
			}
			else
			{
				nu -= (num - 1);
				de += (num - 1);
			}
		}
		n++;				
	}

	printf("%d/%d", nu, de);

	return 0;
}