Algorithm - 분수찾기 (Java)

🌴 문제

---

 

문제

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

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)가 주어진다.

출력

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

예제 입력 1 복사

1

예제 출력 1 복사

1/1

예제 입력 2 복사

2

예제 출력 2 복사

1/2

예제 입력 3 복사

3

예제 출력 3 복사

2/1

예제 입력 4 복사

4

예제 출력 4 복사

3/1

예제 입력 5 복사

5

예제 출력 5 복사

2/2

예제 입력 6 복사

6

예제 출력 6 복사

1/3

예제 입력 7 복사

7

예제 출력 7 복사

1/4

예제 입력 8 복사

8

예제 출력 8 복사

2/3

예제 입력 9 복사

9

예제 출력 9 복사

3/2

예제 입력 10 복사

14

예제 출력 10 복사

2/4

 

 

 

 

 

 

🌴 문제 분석

---

 

• 분모 값과 분자 값의 합을 T 라고 할 때 다음과 같은 규칙이 생긴다. (파란색 -  짝수,  빨간색 - 홀수 )
• 대각선 칸의 개수는 T - 1 개다.

예)
X=14 번째 원소 출력 // 
prev_count_sum 직전 대각선까지의 원소 개수// 

T=2 일 때는 prev_count_sum = 0,
T=3 일 때는 prev_count_sum = 1,
T=4 일 때는 prev_count_sum = 3,
T=5 일 때는 prev_count_sum = 6,
T=6 일 때는 prev_count_sum = 10

T=6일 때, (X - prev_count_sum )하면 14-10=4 로 '현재 대각선에서 4번째 원소 // 
4번째 원소라는 것은 즉, 분모 혹은 분자가 4 // 
현재 대각선의 원소의 개수(cross_count : T=6일 때 5개)에서 '몇 번째'원소인지를 빼주기 // 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class day17 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// 분수찾기
		// T % 2 가 0 일 때는 대각선 위 방향, 1 일 때는 아래 방향으로 진행
		// n번째 대각선은 n개의 개수
		//입력받을 X 값
		//해당 범위의 대각선 칸 개수 ( cross_count )
		//해당 대각선 직전 대각선 까지의 칸의 누적 합 ( prev_count_sum )
		
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int X = Integer.parseInt(br.readLine());
	
	
	int cross_count = 1;
	int prev_count_sum = 0;
	

	while (true) {
		// 직전 대각선 누적합 + 해당 대각선 개수 이용한 범위 판별
		if (X <= prev_count_sum + cross_count) {
			
			if (cross_count % 2 == 1) {  // 대각선의 개수가 홀수라면
				
				// 분자는 대각선상 블럭의 개수 - (x번째 - 직전 대각선까지의 블럭 개수 - 1)   => 대각선의 개수와 분모와 분자의 합 차이가 1이라서  -1 1
				// 분모는 x 번째 - 직전 대각선까지의 블럭 개수
				System.out.println((cross_count - (X - prev_count_sum - 1)) + "/" + (X - prev_count_sum));
				break;
			}
			
			
			else { // 대각선의 개수가 짝수라면
				   // 홀수 반대로 출력
				System.out.println((X - prev_count_sum) + "/" +(cross_count - (X - prev_count_sum - 1)));
				break;
			}
			
		} else {
			prev_count_sum += cross_count;
			cross_count++;
		}
	}
	}

}

 

* 참고 

https://st-lab.tistory.com/74

---