[BackJoon]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)가 주어진다.

 

출력

 

첫째 줄에 분수를 출력한다.

 

풀이

 

지난 문제의 계차수열에 이어 이번엔 군수열이다. 주어진 순서에 따라 분자, 분모는 각각

 

• 분자 - (1), (1, 2), (3, 2, 1), (1, 2, 3, 4) , (5, 4, 3, 2, 1),...
• 분모 - (1), (2, 1), (1, 2, 3), (4, 3, 2, 1) , (1, 2, 3, 4, 5),...

와 같이 변한다. n 번째 군을 이루는 항의 개수는 n 개이기 때문에 주어진 숫자가 몇 번째 군의 몇 번째 항인지만 알아내면 된다.

 

먼저 주어질 숫자의 범위를 역산해 4472까지 IntStream을 열어 몇 번째 군인지 판별했고,

 

계산을 편하게 하기 위해 아래와 같이 조작했다.

 

• 분자 - (1), (1, 2), (1, 2, 3), (1, 2, 3, 4) , (1, 2, 3, 4, 5),...
• 분모 - (1), (2, 1), (3, 2, 1), (4, 3, 2, 1) , (5, 4, 3, 2, 1),...
• 홀수 번째 군일 땐 분자와 분모 자리 바꾸기

이렇게 해두면 주어진 숫자 x의 분자 num은 n번째 군에 속하며, 그 일반항은 아래와 같이 된다.

 

$$num=x - \frac{n^{2} - n}{2}$$

 

분모 den은 더 간단하다.

 

$$den = 1 + (n - num)$$

 

홀수 번째 군일 때 분자, 분모를 뒤집는 것도 잊어선 안 된다.

import java.util.Scanner;
import java.util.stream.IntStream;

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

        int x = sc.nextInt();

        int n = IntStream.rangeClosed(0,4472)
                .filter(a -> (a * a + a) / 2 < x)
                .map(a -> a + 1)
                .max()
                .getAsInt();

        int num = x - (n * n - n)/2;
        int den = n - num + 1;

        if(n % 2 == 0) System.out.println(num+"/"+den);
        else System.out.println(den+"/"+num);
    }
}