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

문제

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

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.
X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

---

문제 풀기 전 로직생각

1. x를 입력받고 그것이 지그재그 형태로 몇번재 라인인지 판단. 예를들어 2/1과1/2은 2번째라인, 3/1,2/2,1/3은 3번째라인
2. x값이 line보다 작아질때까지 반복문을 돌리며 x를 line만큼 빼주고 line은 1씩 증가하며 반복
3. 그럼 라인과 x값이 재계산됨.
4. 이때 line이 짝수면 x값이 분모로, 홀수면 분자로 그대로 들어가는것을 확인 할 수 있음.
5. 그 외는 line-x+1을 해주면 됨.

코드

#include <iostream>
using namespace std;

int main() {

	int x;
	cin >> x;

	int line = 1; //몇번째 줄인지

	while (x > line) {
		x -= line; //대각선이 1/1부터 1개   (1/2,2/1) 2개   (1/3, 2/2, 3/1) 3개로 점차 증가함
		line++; //대각선의 원소갯수를 위해 증가시킴.
	}
	/*
	line 1
	1 -> 1,1

	line2
	2 -> 2,1 1/2
	3 -> 2,2 2/1

	line3
	4 -> 3,1 3/1
	5 -> 3,2 2/2
	6 -> 3,3 1/3

	line4
	7 -> 4,1 1/4
	8 -> 4,2 2/3
	9 -> 4,3 3/2
	10 ->4,4 4/1

	규칙
	1. line이 짝수면 계산된 x값은 은 분모로간다. 홀수면 분자로
	2. 짝수면 분자값은 거꾸로 올라가듯 x가 증가하니 line-x에서 1더하기까지
	*/
	if (line % 2 == 0) 
		cout << x << "/" << line-x +1;
	else
		cout << line-x +1 << "/" << x;
	
	return 0;
}

결과

 

 

아마 풀때 x값이 바뀌면서 혼동이 올 수 도 있는데,

바뀐 x값은 각 라인에서 몇번째에 배치되어 있는지(대각선으로 초기x값이 5일경우 3번째 대각선라인에서 2번째에 배치,

초기값이 9일경우 4번째 대각선에서 3번째에 위치)를 나타내게 되더라구요.

 

문제부터 이해하기 어려웠고, 규칙도 찾기 힘들어서 검색을 통해 알아내고 이해를 토대로 풀었습니다.

검색없이 풀었으면 이것보다 코드가 더러웠을거라 생각합니다.