[P&B] #69 BAEKJOON 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.*;
public class bj1193 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int X = Integer.parseInt(br.readLine());
        int count = 1;
        int sum = 0;
        while (X > count) {
            X -= count;
            sum += count;
            count++;
        }

        int number = count+1;
        int nume = 0;
        int deno = 0;

        if (count%2 == 1){
            nume = number - X;
            deno = X;
        }
        else {
            deno = number - X;
            nume = X;
        }
        bw.write(nume +"/"+ deno);
        bw.flush();
    }
}

 

문제 풀이 코멘트

네.. 또 규칙 문제입니다......ㅎr...

처음에 지그재그 순서가 무슨말인지 몰랐는데 예제를 보고 이해했습니다.

각 대각선을 하나의 라인이라고 한다면 지그재그 순서의 분수는 다음과 같습니다.

(n번째 라인 - n번째 라인에 속하는 분수들)

1 - 1/1
2 - 1/2 2/1
3 - 3/1 2/2 1/3
4 - 1/4 2/3 3/2 4/1
5 - 5/1 4/2 3/3 2/4 1/5

따라서, X번째 분수를 찾기 위해 다음과 같은 단계를 따를 수 있습니다:

1. 대각선을 몇 번째 대각선인지 찾습니다.
2. 해당 대각선에서 X번째 분수가 몇 번째 분수인지 계산합니다.
3. 대각선의 번호와 분자, 분모를 사용하여 X번째 분수를 찾습니다.

제가 푼 코드는 사실 통과되긴 했지만 완전한 정답은 아닙니다. 짝수번째,홀수번째인지 판별하는 부분에서 카운팅이 잘못되는 느낌..?

그래서 아래의 클린코드를 첨부해둡니다.

설명을 보고 아래의 코드를 보면 이해하기 쉬울것입니다.

import java.io.*;

public class bj1193 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int X = Integer.parseInt(br.readLine());

        int diagonal = 1; // 대각선 번호
        int sum = 0; // 대각선에서 분자와 분모의 합

        // 대각선 번호와 대각선에서 분자와 분모의 합을 계산
        while (sum + diagonal < X) {
            sum += diagonal;
            diagonal++;
        }

        int numerator; // 분자
        int denominator; // 분모

        // 대각선 번호가 홀수인 경우
        if (diagonal % 2 == 1) {
            numerator = diagonal - (X - sum - 1);
            denominator = X - sum;
        } 
        // 대각선 번호가 짝수인 경우
        else {
            numerator = X - sum;
            denominator = diagonal - (X - sum - 1);
        }

        bw.write(numerator + "/" + denominator);
        bw.flush();
    }
}