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

 

출력

 

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

 

풀이

 

수열을 조금 더 늘어놓고 규칙 및 풀이 방법을 찾아보자.

$$\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{3}{1}, \frac{2}{2}, \frac{1}{3}, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1},  ...$$ 

1. 분모 → 분자 순서로 (1), (1, 2), (1, 2, 3), (1, 2, 3, 4), ... 의 군수열을 이루고 있다.
2. 분자 → 분모 순서로 (1), (2, 1), (3, 2, 1), (4, 3, 2, 1), ... 의 군수열을 이루고 있다.
3. 홀수 번째 군의 분수는 1번이 분모, 짝수 번째 군의 분수는 2번이 분모가 된다.
4. 등차수열의 합과 입력받는 숫자(x)를 이용해 몇 번째 군(n)의 몇 번째 항인지 계산해 해당 항을 찾는다.
5. 입력 최대치가 10,000,000이므로, 등차수열의 합 공식에 의해 4472번째 군수열 까지만 순회한다.

참고로 첫째항이 a이고 n번째 항이 l인 등차수열의 합은 아래와 같다.

$$S_{n}=\frac{n(a+l)}{2}$$

 

설명이 길었지만 코드로 보면 간단하게 아래와 같다.

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); // 홀수 번째 군일 경우
    }
}

4000
6/84