[BAEKJOON_1193] 분수찾기

[BAEKJOON_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

해결

분모 기준 : 행에서 1식 증가하여 좌측 대각선으로 감소
분자 기준 : 열에서 1식 증가하여 우측 대각선으로 감소

     분자증가   1/1    분모증가
             2/1, 1/2
           3/1, 2/2, 1/3
         4/1, 3/2, 2/3, 1/4
       5/1, 4/2, 3/3, 2/4, 1/5
        분자 감소 / 분모증가

한다는 것을 볼 수 있다.

1. N번재 분수가 몇 번째 대각선에 위치하는지 알아야한다.
2. 대각선의 기준 합이 몇인지 알아야한다.
3. 대각선의 위치와 합계를 계산했으면 홀수인경우 좌측에서 우측으로(분자 감소, 분모 증가), 짝수인경우 우측에서 좌측으로(분자 증가, 분모감소) 를 계산해준다.

코드

import java.util.Scanner;

    public class Main {

        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            int n = scan.nextInt();

            int sum = 1, cnt = 2;
            //1. N번재 분수가 몇 번째 대각선에 위치하는지 위치 값과 총합을 계산해준다
            while (n > sum) {
                sum += cnt++;
            }

            cnt--;
            sum -= n;

            //2. 홀수인경우 분모감소, 분자증가 짝수인경우 분모감소 분자 증가
            int numerator = (cnt % 2 == 0) ? cnt - sum :  sum +  1;
            int denominator = (cnt % 2 == 0) ? sum + 1 : cnt - sum;

            System.out.println(numerator + "/" + denominator);
        }
    }