백준 1193 - 분수찾기

문제 번호: 1193

문제 제목: 분수 찾기

문제 주소: https://www.acmicpc.net/problem/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 -> ... 과 같은 순서로 진행되는 배열에서 X 번째 분수를 출력한다.

테스트 케이스

1	1/1
4	3/1
6	1/3
7	1/4
1000000000	6282/38440

문제 풀이

1번째 대각선은 1/1
2번째 대각선은 1/2 -> 2/1
3번째 대각선은 3/1 -> ... -> 1/3
4번째 대각선은 1/4 -> ... -> 4/1
5번째 대각선은 5/1 -> ... -> 1/5

짝수 번째 대각선은 1/n -> n/1로 진행되고 (분자 증가, 분모 감소)
홀수 번째 대각선은 n/1 -> 1/n으로 진행된다. (분자 감소, 분모 증가)
따라서 X번째 수는 1 ~ (n - 1)까지의 합계를 X에서 제거한 뒤
n이 짝수인 경우에는 X / (n - X + 1)
n이 홀수인 경우에는 (n - X + 1) / X가 된다.
위 규칙을 적용하여 코드를 작성하면 된다.

풀이 코드

#include <iostream>
using namespace std;

void BAEKJOON_1193()
{
	int X;
	cin >> X;
	int n = 1;
	for (int i = 1; X > i; i++)
	{
		X -= i;
		n++;
	}

	int denominator;
	int numerator;
	if (n % 2)
	{
		denominator = X;
		numerator = n - X + 1;
	}
	else
	{
		denominator = n - X + 1;
		numerator = X;
	}

	cout << numerator << "/" << denominator << endl;
	return;
}