[알고리즘] 백준 1193번 분수찾기 Java

https://www.acmicpc.net/problem/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)가 주어진다.

출력

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

Code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int X = Integer.parseInt(br.readLine());

        int lineNum = 0;
        int lineCount = 0;
        while(true){
            if(lineNum >= X){
                break;
            }
            lineCount++;
            lineNum = lineCount * (lineCount + 1) / 2;

        }

        if(lineCount % 2 != 0){
            System.out.println((lineNum - X + 1) + "/" + (lineCount - (lineNum - X)));
        } else {
            System.out.println((lineCount - (lineNum - X)) + "/" + (lineNum - X + 1));
        }
    }
}

Point

저 분수 배열에서 규칙성을 찾아야 한다.

1/1 lineCount = 1
2/1 1/2 lineCount = 2
3/1 2/2 1/3 lineCount = 3
4/1 3/2 2/3 1/4 lineCount = 4
...

위와 같은 형식으로 진행된다.
일단 X 입력값이 몇번째 줄(lineCount)에 해당하는지와 그 줄까지 총 개수를 구한다.

그리고 노트에 적어가면서 위의 공식을 유도하였다.
lineCount가 홀수와 짝수는 서로 반대방향으로 진행되기에 역수를 취해주면 된다.