[BAEKJOON] 1193번 분수 찾기

---

지그재그로 지나가는 루트를 층 단위의 개념으로 이해해보자.

홀수 층은 대각선 위 방향으로, 짝수 층은 대각선 아래 방향으로 움직인다.

이때 (층수+1)은 각 층에 존재하는 분수의 분모와 분자를 더한 수와 같다.

내가 찾고자 하는 분수가 8번째라고 하면 예제 출력에 의하면 2/3이어야 한다.

1층에 분수 1개, 2층에 분수 2개, 3층에 분수 3개, ... 와 같은 패턴을 보인다.

입력 예제가 몇 층에 위치하는지, 해당 위치의 분수는 어떤 수로 분자와 분모를 이루는지 패턴을 읽어보자.

반복문을 돌면서 해당 층수의 분수 개수를 누적하여 더한다.

1층까지의 누적 분수 개수 => 1개

2층까지의 누적 분수 개수 => 1+2개

3층까지의 누적 분수 개수 => 1+2+3개

4층까지의 누적 분수 개수 => 1+2+3+4개

입력 받은 분수 위치(8)보다 누적 분수 개수(10개)가 작다면 해당 층(4층)에 찾고자 하는 분수가 위치해있을 것이다.

이제 4층에 위치 8인 분수가 존재하는 걸 알았으니 분모와 분자가 어떤 수로 이루어져있는지 알아본다.

홀수층일 경우 대각선 위 방향으로 분자는 해당 층수에서 1씩 감소하고, 분모는 1에서부터 해당 층수까지 1씩 증가한다.

반대로 짝수층의 경우, 대각선 아래 방향으로 분자는 1에서부터 해당 층수까지 1씩 증가하고, 분모는 해당 층수에서부터 1까지 1씩 감소하는 패턴을 보인다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int floor=0, sum=0;
		while(true) {
			floor++;
			sum += floor;
			if(sum >= n) {
				if(n%2==0) {
					System.out.println(n-sum+floor+"/"+(sum-n+1));
				}else {
					System.out.println((sum-n+1)+"/"+(n-sum+floor));
				}
				break;
			}
		}
	}
}

[출처]

https://www.acmicpc.net/problem/1193

1193번: 분수찾기