[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
        분자 감소 / 분모증가

한다는 것을 볼 수 있다.

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

대각선 번호와 내부 위치

분자와 분모의 합이 같은 칸끼리 하나의 대각선을 이룬다. 첫 대각선에는 1개, 둘째에는 2개, d번째에는 d개의 분수가 있다. 따라서 d번째 대각선까지 방문한 칸의 수는 삼각수 T(d)=d(d+1)/2이다. X를 포함하는 가장 작은 d를 찾으면 그 대각선 안의 순서는 p=X−T(d−1)이다.

둘째 대각선은 1/2, 2/1처럼 분자가 증가하고, 셋째는 3/1, 2/2, 1/3처럼 감소한다. 짝수 d에서는 분자=p, 분모=d−p+1이고 홀수 d에서는 분자=d−p+1, 분모=p다. X=14이면 T(4)=10, T(5)=15이므로 d=5, p=4다. 홀수 대각선의 네 번째 칸은 2/4가 된다.

코드의 sum은 처음에는 누적 삼각수이고, sum -= n 뒤에는 대각선 끝에서 X까지 남은 칸 수로 뜻이 바뀐다. 이 변수의 의미 변화를 놓치면 홀짝 식이 반대로 보일 수 있다. X=1은 첫 대각선에서 1/1, X가 삼각수와 같으면 해당 대각선의 마지막 분수다. 대각선을 하나씩 찾는 현재 구현은 O(√X) 시간과 O(1) 추가 공간을 쓴다.

대각선의 경계를 먼저 적어 보면 홀짝 방향을 검산하기 쉽다.

d	이 대각선의 순번	방문 순서
1	1	1/1
2	2~3	1/2, 2/1
3	4~6	3/1, 2/2, 1/3
4	7~10	1/4, 2/3, 3/2, 4/1

X=10은 네 번째 대각선의 마지막이어서 4/1이고, X=11은 다음 대각선의 첫 칸 5/1이다. 대각선이 바뀌는 곳에서 분자·분모 증가 방향도 바뀌므로 이 두 값은 짝을 이루는 경계 테스트다.

코드

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);
        }
    }