무지개 달팽이

Q. 무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

이와 같이 나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력.

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력.

첫째 줄에 분수를 출력한다.

"해당하는 레벨 구하기 + 그 레벨에서 몇 번 째 분수인지 구하기"

표를 트리 모양으로 바꿔서 생각해보면, 

홀수번 째 레벨 : 분자 감소, 분모 증가  /  짝수번 째 레벨 : 분자 증가, 분모 감소

위와 같은 규칙을 발견할 수 있다.

그리고 입력받은 수의 레벨이 몇 번 째인지 알아내기 위해, x을 대입한 변수 tmp에 변수 cnt의 값을 빼주면서 cnt > tmp가 되는 구간을 찾아낸다. 이 반복문을 끝냈을 때 나온 변수 tmp의 값은 해당 레벨에서 몇 번 째 분수인지 알아내는데 사용한다.

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

int main(void)
{
	int x;			

	int i, tmp, cnt;	

	int child, parent;

	scanf("%d", &x);

	if (x == 1)
		printf("1/1");
	else {

		cnt = 1;

		tmp = x;

		while (tmp > cnt)
		{
			tmp -= cnt;
			cnt++;
		}

		if (cnt % 2 == 0)
		{
			parent = cnt; child = 1;

			for (i = 1; i < tmp; i++)
			{
				parent--;
				child++;
			}
		}
		else
		{
			parent = 1; child = cnt;

			for (i = 1; i < tmp; i++)
			{
				parent++;
				child--;
			}
		}

		printf("%d/%d", child, parent);
	}

	return 0;
}