백준] 1193 - 분수찾기

시간 제한 : 2초

메모리 제한 : 128MB

입력

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

출력

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

소스코드

#include <iostream>
using namespace std;
int main(void)
{
	int n, k = 1;
	cin >> n;
	while (1)
	{
		if (k*(k + 1) / 2 == n)
		{
			if (k % 2 == 0)
				cout << k << "/" << 1;
			else
				cout << 1 << "/" << k;
			break;
		}
		else if (k*(k + 1) / 2 > n)
		{
			if (k % 2 == 0)
			{
				int cnt = n - k*(k - 1) / 2;
				cout << cnt << "/" << k - cnt + 1;
			}
			else
			{
				int cnt = n - k*(k - 1) / 2;
				cout << k - cnt + 1 << "/" << cnt;
			}
			break;
		}
		k++;
	}
	return 0;
}

Tip

사선 방향 규칙만 잘 풀어낼 수 있으면 쉽게 해결 가능하다.