[Java] 백준 1193번: 분수 찾기

변수 정의

다음과 같이 인덱스가 1부터 시작해서 대각선으로 분수들을 묶는다.
이 배열들이 담긴 배열의 인덱스를 n이라고 하자.
예를 들어, n=4인 줄은 1/4가 속한 줄이다.

참고로 n번째 줄에 들어있는 분수의 개수는 n개이다.

그런데 몇번째 줄인지에 따라서 분수배열의 대각선 방향 진행 방향이 달라진다.
n이 짝수 일 때는 1/n부터 진행하고, 홀수인 경우에는 n/1부터 진행한다.

이 때, 진행하는 방향부터 시작해서 인덱스를 지정하고, 이를 y라고 하자.

예를 들어서, 그림처럼 '4/2'는 5번째 줄의 2번째 분수이기에, n=5이고 y=2이다.

식 세우기

그렇다면 이제 x를 통해서 n과 y를 정의하는 식을 세워야한다.

만약 n번째 줄에 x가 있다면, x는 1부터 n까지의 합보다 작거나 같은 값일 것이다. 여기서 x에서 1부터 n-1번째 줄까지의 합을 빼준다면, x가 n번째 줄의 몇번째 분수인지, 즉 y가 정의된다.

그리고 이를 통해서 구한 n과 y를 통해서 x번째의 분수를 찾는 식을 세우면 다음과 같이 세울 수 있다.

코드 구현

이를 코드로 구현한 모습은 다음과 같다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		int x = Integer.parseInt(rd.readLine());
		int n = 1;
		int y;
		while(true) {
			if(x <= n * (n + 1) / 2) { // 'x ≦ 1~n까지의 합'을 만족하는 n들 중, 최소 n에 대하여, x는 n번째 줄에 속한다.
				y = (x - n * (n - 1) / 2); // 그러한 x가 발견되면 y도 함께 정의.
				break;
			}
			n++;
		}
		System.out.println(
			//n이 짝수일 때와 홀수인 경우를 나누어서 삼항연산자를 이용해 출력.
			(n % 2 == 0 ? (1 + (y - 1)) +"/"+ (n - (y - 1)) : (n - (y - 1)) +"/"+ (1 + (y - 1))));
	}
}