[백준] 1193번 분수찾기

1193번: 분수찾기

주어진 순서대로 번호를 매긴 후 점선을 기준으로 그 범위의 최댓값만 나열하니

계차 수열이 나왔다. 계차수열 an을 구한다.

 

i가 0부터 1씩 늘어난다면

n이 짝수인 경우 분수는 n-i/i+1

홀수인 경우 분수는 i+1/n-i 의 형태가 된다.

​

이런 공식을 찾기만 한다면 끝

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