[백준][c] 1193번: 분수찾기

https://www.acmicpc.net/problem/1193

1193번: 분수찾기

 

문제

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

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)가 주어진다.

출력

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int	group(int _n) {	//n이 몇번째 그룹에 속하는지 반환
	int i;
	for (i = 1; !((i-1)*(i) / 2 < _n && _n <= (i)*(i+1) / 2)   ; i++)
	{
		//비어있음
	}
	return i;
}


int in_group(int _n) {	//그룹 안에서 몇번째 인지 반환
	int i;
	for (i = 1; !((i - 1) * (i) / 2 < _n && _n <= (i) * (i + 1) / 2); i++)
	{
		//비어있음
	}
	return _n - (i - 1) * (i) / 2;
}

int main() {
	int n, top, bottom;
	
	scanf("%d", &n);
	
	if (group(n) % 2)
	{
		top = group(n) - in_group(n) + 1;
		bottom = in_group(n);
	}
	else
	{
		bottom = group(n) - in_group(n) + 1;
		top = in_group(n);
	}
	printf("%d/%d", top, bottom);
}

문제풀이

규칙성을 이용한 수학문제였습니다. 우선 분수의 진행방향을 잘 파악하셔야합니다. ( 글쓴이는 진행방향을 반대로 생각하고 문제를 풀어서 처음에 틀렸음) 홀수번 그룹에서는 좌에서 우로, 짝수번 그룹에서는 우에서 좌로 오는 것입니다.

몇 번째 그룹인지와, 그룹 내에서의 번호를 알아내어 분모와 분자 각각을 알아낼 수 있기에, 따로 함수를 작성했습니다. 마지막으로 홀수번/짝수번 그룹을 나누어서 top과 bottom을 뒤바꿔주면 되겠습니다.

비고

문제를 풀기에 앞서 규칙을 정확히 파악해야겠습니다. 첫 단추를 잘 꿰매지 못해서 엉망이 됐습니다!!!