문제

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

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/2 -> 2/1 ->
3/1 -> 2/2 -> 1/3 ->
1/4 -> 2/3 -> 3/2 -> 4/1 ->
5/1 -> 4/2 -> 3/3 -> 2/4 -> 1/ 5 ->

이와 같이 진행됨을 알수 있다. 1개 2개 3개 4개 등차 수열로 진행되며 N번째 항의 갯수는 n * (n+1) / 2개이다. 또한 홀수 일때와 짝수일때 시작하는 분수가 다르니 이를 유의해야 한다.

먼저 등차수열 항의 갯수 공식을 이용하여 입력으로 주어지는 X가 어디에 속하는지(line) 찾아야 한다. 그 후 line의 값이 짝수일 때와 홀수 일때를 나눠서 출력하면 된다.

주어진 예시로 (x = 14) 예를 들어보자.
Line : 1 2 3 4 5
Count : 1 3 6 10 15

line이 5일때 x가 포함되어 있다. 그 후 line이 홀수이기 때문에 분자에는 count - x + 1의 값이 들어가고 분모에는 line - (count - x)가 들어간다.

count - x를 해주는 이유는 x의 위치를 파악하기 위해서이다.

소스

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int x = sc.nextInt();

		if (x == 1) {
			System.out.println(1 + "/" + 1);
		} else {
			int line = 1;
			int count = 1;

			while (count < x) {
				line += 1;
				count = (line * (line + 1)) / 2;
			}

			int up = 0, down = 0;

			// 짝수 줄일 때
			if (line % 2 == 0) {
				up = line - (count - x);
				down = count - x + 1;
				System.out.println(up + "/" + down);
			}
			// 홀수 줄일 때
			else {
				up = count - x + 1;
				down = line - (count - x);
				System.out.println(up + "/" + down);
			}

		}

	}

}