백준 1193번 : 분수찾기 c언어

문제

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

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

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

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

입력

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

출력

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

예제 입력 1 복사

1

예제 출력 1 복사

1/1

예제 입력 2 복사

2

예제 출력 2 복사

1/2

 

코드

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
	int n,num=0,cnt=1,chknum,u,d;
	scanf("%d", &n);
	while (num + cnt < n)
	{
		num = num + cnt;
		cnt++;
	}
	if (cnt % 2 == 1)
	{
		u = cnt+1;
		d = 0;
		chknum = n - num;
		while (chknum > 0)
		{
			u--;
			d++;
			chknum--;
		}
		printf("%d/%d", u, d);
	}
	else
	{
		u = cnt+1;
		d = 0;
		chknum = n - num;
		while (chknum > 0)
		{
			u--;
			d++;
			chknum--;
		}
		printf("%d/%d", d, u);
	}
}

코드설명

표를 보면 공토적으로 대각선을 한줄이라고 생각했을때 홀수는 분자가 줄어들고 분모가 늘어나는 짝수는 분자가 늘어나고 분모가 줄어드는 형태의 공통점을 찾을수있었다. 이것을가지고 코드를 짜야겠다는 생각이 들었다. 

먼저 몇번째줄에 있는지를 판단하기위해 반복문을 이용해 num(기준이되는 줄 이전에 나온 분수수 개수의 총합)+cnt(기준이 되는 줄이 몇번째인지)<n(찾아야되는 수가 몇번째에 있는지)라는 식으로 몇번째에 있는지를 찾아주었다. 그 후 cnt가 홀수라면 분자가 줄어들고 분모가 늘어나는 짝수라면 분자가 늘어나고 분모가 줄어드는 형식으로 반복문을 짜서 풀었다.

 

느낀점

확실히 단순히 반복문을 사용하지 않으려고하니 수학을 못해서 그런지 머리가 복잡하다. 그래도 더 연습해가면서 좀더 단순하고 빠르게 풀수있도록 노력해야겠다.