[C++] 백준 1193번 분수찾기 :: seoftware

문제

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

1193번: 분수찾기

소스코드

#include <iostream>
using namespace std;

int main(void) {
	int X; cin >> X;
	
	if (X == 1) {
		cout << "1/1" << endl; return 0;
	}
	int n = 1;
	while (1) {
		//종료조건
		if ((n+2)*(n + 1) / 2 >= X) break;
		n++;
	}
	int rest = X - n * (n + 1) / 2;
	int up, down;
	if (n % 2) {
		up = rest; down = n - rest + 2;
	}
	else {
		up = n - rest + 2; down = rest;
	}
	cout << up << '/' << down << endl;
}

코드설명

1. n까지의 합은 n*(n+1)/2 입니다. X 이하의 n의 최댓값을 구합니다. (while문)

2. X에서 n*(n+1)/2 이 값을 빼주어서 [0, n] 또는 [n, 0]에서 몇 칸이나 더 움직여야 하는지 계산합니다.

3. n이 짝수일 때와 홀수 일 때로 나누어서 분자와 분모를 구해줍니다. n이 만약 홀수라면 X는 n+1 그룹에 속하므로 시작하는 분수[n, 0]에서 오른쪽 위로 올라갈 것이고, 짝수라면 시작하는 분수[0, n]에서 왼쪽 아래로 내려갈 것입니다.