[JAVA] 백준 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.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt(); // 입력 받은 수

        // count = 1일 때
        if (count == 1) {
            System.out.print(1 + "/" + 1);
        }

        else {
            // res 는 숫자그룹의 끝번호
            int res = 0;
            // a는 전 숫자그룹의 끝번호를 알 수 있는 변수
            int a = 0;
            for (int i = 0; res < count; i++) {
                res += i;
                a = i;
            }


            // count가 속한 숫자그룹의 끝번호 res가 나왔다면 if문
            // 홀수라면 작은숫자->큰숫자 순으로 분수 만들기

            ArrayList<String> list = new ArrayList<>();

            // 짝수 합계 일 때
            if (a % 2 != 0) {

                int y = count - (res - a+1);
                for (int i = a; i > 0; i--) {
                    for (int j = 1; j <= a; j++) {
                        if (i + j == a + 1) {
                            list.add(i + "/" + j);
                            break;
                        }
                    }
                }
                System.out.print(list.get(y));

            }

            // 홀수 합계일 때
            else {
                int x = count - (res - a+1);
                for (int i = 1; i < a + 1; i++) {
                    for (int j = a; j > 0; j--) {
                        if (i + j == a + 1) {
                            list.add(i + "/" + j);
                            break;
                        }
                    }
                }
                System.out.print(list.get(x));

            }


        }
    }

}

 

 

 

 

대각선의 합을 구하면 숫자가 1씩 늘어나는 알 수 있는데,

홀수는 아래로, 짝수는 위로 향한다. 

이를 유의해서 풀면 된다.