[Problem Solving/Java] 백준 1193번 - 분수찾기

https://www.acmicpc.net/problem/1193

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

출력

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

첫 번째 시도

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int a = Integer.parseInt(br.readLine());
        int seq = 0;
        int num = 0;
        int denominator = 0;
        int numerator = 0;

        for (int i = 1; seq < a; i++) {
            seq = seq + i;
            System.out.println(seq + " " + i);
            num = i;
        }

        if (num % 2 == 0) {
            numerator = seq + 1 - a;
            denominator = num + 1 - numerator;
            System.out.println(denominator + "/" + numerator);
        } else {
            numerator = seq + 1 - a;
            denominator = num + 1 - numerator;
            System.out.println(numerator + "/" + denominator);
        }
    }
}

해결 방법

각 대각선 마다 자연수가 a-i/i 의 형태로 표현되었다. 여기서 분자 분모를 더하면 a인데 이 a는 대각선 순서+1이다. 대각선 순서는 num으로 나타냈다. Num은 seq를 통해 계산할 수 있었는데, Seq는 1+2+3+4+ … 의 계산식으로 나타냈다. 여기서 num은 덧셈을 한 횟수이다. 따라서 주어진 수가 Seq에서 어느 단계에 해당하는지 num으로 구한다. 분자는 num이 홀수일 때, 짝수일 때 나눠서 구했다. Num이 짝수일때는 분자가 1에서 시작하고, num이 홀수일 때는 분자가 num에서 시작했다. 식을 일반화해서, 분자는 seq-a+1로 구했고, 분모는 num+1-분자로 구했다. 그래서 if문을 통해 짝수이면 분자 분모를 반대로, 홀수이면 분자 분모를 그대로 출력했다.