백준 / 수학 / 1193번 / 분수찾기 / C++

문제

 

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

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 → … 과 같은 지그재그 순서로 차례대로
1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

 

#include <iostream>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	// x번째 분수 
	int x;
	cin >> x;
	
	// 첫번째 대각선의 분수의 개수 = 1 
	int i = 1; // i번째 대각선 
	 
	while(x > i) {
		x -= i;
		i++;
	}
	
	// 홀수번째 대각선에서는 분자가 i부터 시작
	if(i % 2 == 1) {
		// i번째 대각선에는 i개의 분수가 있음.
		// x는 i번째 대각선에서 몇번째에 있는지 나타냄.
		cout << i - x + 1 << "/" << x << '\n';
	} 
	else {
		cout << x << "/" << i - x + 1 << '\n';
	}
	
	return 0;
}

---

조금 헷갈렸지만 간단한 문제이다.

경로를 그려보면 

1/1 을 첫번째 대각선이라고 할때, 홀수번째 대각선에서는 위로가고,

짝수번째 대각선에서는 아래로 간다.

 

다시 코드에서 반복문을 보면, i가 1부터 시작해서 x -= i;를 해주고 i++를 해준다.

표를 보면 i번째 대각선에는 i개의 분수가 있는것을 알 수 있다.

따라서 입력받은 x에서 i번째의 분수의 개수를 순차적으로 빼주는것이다.

 

만약 x로 14를 입력받았다면, 14에서 1,2,3,4를 빼주는 것이다.

그러면 x는 4가되고 빼준 후에 마지막에 i++를 해주었기 때문에 i=5가 되고 반복문은 종료된다.

 

x=4, i=5가 의미하는것은 i번째 대각선에서 x번째 분수라는 뜻이다.

5번째 대각선을 살펴보면 분자의 규칙성이 있다.

i-0, i-1, i-2, i-3, i-4로 분자의 순서가 이어진다.

따라서 분자를 구하려면 i-x+1을 해주면된다.

 

결론적으로 i가 홀수일때, 즉 화살표가 위로갈때는 i-x+1/x 이고,

짝수일때, 즉 화살표가 아래로갈때는 x/i-x+1이 된다.