[백준] 1193번: 분수찾기 - JAVA

[작성일: 2023. 09. 22]

 

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

 

 

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        sc.close();

        int line = 0;  // 대각선 번호
        int sum = 0;  // 분자+분모의 합

        while (num > sum) {
            line++;
            sum += line;
        }

        int top = 0;
        int bottom = 0;

        // 대각선이 짝수일 경우
        if (line % 2 == 0) {
            top = line - (sum - num);
            bottom = 1 + (sum - num);
        } else {  // 대각선이 홀수일 경우
            top = 1 + (sum - num);
            bottom = line - (sum - num);
        }

        System.out.println(top + "/" + bottom);

    }
}

 

분수를 나열하다 보면 패턴이 보이는데 지그재그 순서로 차례대로 나열할 때, 각 대각선 방향에 있는 분수들의 분자와 분모의 합이 동일한 것을 확인할 수 있다.

 

1/1 -> 합: 2

1/2 -> 2/1 -> 합: 3

3/1 -> 2/2 -> 1/3 -> 합: 4

...

이런 식으로 진행된다.

 

주어진 num이 어느 대각선에 속하는지 알아낼 수 있으면 해당 대각선의 처음이나 끝에서부터 num번째 분수를 구할 수 있다.