[백준/java] 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)가 주어진다.

출력

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

 

※ 도출 과정

1 1 1 1 2 1 3 1 4 1 5 1 6 
0 0 1 2 3 0 1 2 3 0 1 2 3

1	1	1	1	2	1	3	1	4	1
0	0	1	2	3	0	1	2	3	0

이런식으로 갯수가 늘어남.

인덱스가 1,3인 경우에만 다음 차례에 이동거리가 +2가 증가함

 

n1과 n2가 뭔가 바뀌었지만 그래도 맞는 소스코드임.

package boj;

import java.util.Scanner;

public class FindFraction {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		
		int n1 = 0, n2 = 1;
		
		int[] dir = {1,1,1,2};	// dir : 0 == ↓, dir : 1 == ↗, dir : 2 == →, dir : 3 == ↙
		int dirIdx = 0;
		int size = 1, cir = -1;
		for (int i = 1; i <= n; i++) {
			if(dirIdx == 0) n1++;
			if(dirIdx == 1) { n1--; n2++; }
			if(dirIdx == 2) n2++;
			if(dirIdx == 3) { n1++; n2--; }
			
			++cir;
//			System.out.println("size : " + size + ", cir : " + cir + ", n1 : " + n1 + ", n2 : " + n2 + ", dirIdx : " + dirIdx);
			if(size == cir) {
				dirIdx++;
				dirIdx %= 4;
				
				if((dirIdx == 0 && n2 == 1) || (dirIdx == 2 && n1 == 1)) {
					size = 1; cir = 0;
				} else {
					size = dir[dirIdx]; cir = 0; dir[dirIdx] += 2;
				}
				
			}
		}
		
		System.out.println(n2+"/"+n1);
		
	}
}