[BOJ/Step8] 1193 : 분수찾기 (JAVA)

www.acmicpc.net/problem/1193

1193번: 분수찾기

---

문제

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

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

 

출력

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

 

예제 입력

14

 

예제 출력

2/4

---

풀이

해당 배열은 지그재그 순서로 번호가 붙여지기 때문에, 다음 그림과 같이 첫번째 대각선에 한개, 두번째 대각선에 두개, n번째 대각선에 n개의 분수가 위치하게 된다. 또한 짝수번째 대각선에 분모 내림차순, 분자 오름차순 / 홀수번째 대각선에 분모 오름차순, 분자 내림차순으로 숫자가 정해지는 것을 볼 수 있다.

1. 입력받은 x와 같은지 확인할 xis, 몇번째 대각선인지 확인할 n을 1로 초기화

2. while문과 for문은 xis가 x와 같을때까지 반복, 한번에 break

3. for문은 n번째 대각선의 분수 개수만큼(=n) 반복. n을 증가시키면서 n의 내부에서 xis를 증가시킨다.

4. x와 xis가 같아졌을 때, n이 홀수인지 분수인지 판단하여 분모 분자 출력

 

import java.util.Scanner;

public class B1193 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int x = sc.nextInt();
		int xis = 1;
		int n = 1;
		
		Loop1 :
		while(true) {
			for(int i = 1; i <= n; i++) {
				if(x == xis) {
					if(n % 2 == 0) {
						System.out.println( i + "/" + (n-i+1) );
					} else {
						System.out.println( (n-i+1) + "/" + i );
					}
					break Loop1;
				}else {
					xis++;
				}
			}
			n++;
		}
	}
}