BOJ-1193 | 분수찾기 c++

✏️ 1193-분수찾기
🌊 GitHub @xaesu, Study-Algorithm

접근

✔️ 수학적 규칙찾기

대각선 방향으로의 접근을 각 행으로 정리하면,
1행 - 1/1
2행 - 1/2 2/1
3행 - 3/1 2/2 1/3
4행 - 1/4 2/3 3/2 4/1
5행 - ...

이때, 아래와 같은 규칙이 성립한다.

1. 각 행에 속하는 요소는 n행일 때 n개가 속함
2. 짝수 행일 때는 분자가 분모보다 작을 때부터
   홀수 행일 때는 분자가 분모보다 클 때부터 나열됨
3. 짝수 행을 기준으로, 분자는 1부터 n까지 하나씩 증가하고 분모는 n부터 1까지 하나씩 감소
   (홀수 행은 분자, 분모 반대로)

몇 행인지 파악하기 ❔
→ 입력 값 x로부터 1부터 차례로 빼며 더이상 뺄 수 없을 때의 값을 구함

풀이

#include <iostream>
using namespace std;

int main() {
	int x;
	cin >> x;

	int a(0), b(0);		// 출력 변수

	// 대각선 행 체크(order)
	// x는 각 행에서의 순서가 됨
	int order(1);
	while (x > order) {
		x -= order++;
	}

	// 행이 짝수이면 오름차순 홀수이면 내림차순
	int is_even = (order % 2 == 0);
	if (is_even) {
		a = x;
		b = order - (x - 1);
	}
	else {
		a = order - (x - 1);
		b = x;
	}

	// 출력
	cout << a << '/' << b;
}