[BOJ] 백준 1193 분수찾기-java

문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

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

출력

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

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

 

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int num=in.nextInt();
        int tmp=0,divisor=0,dividend=0;
        for(int i=1; i<10000; i++) {
            if(num>tmp && tmp+i>=num) {
                if(i%2==0) {
                    divisor=i+1-(num-tmp);
                    dividend=(num-tmp);    
                }
                else {
                    divisor=(num-tmp);
                    dividend=i+1-(num-tmp);
                }
                break;
            }
            tmp+=i;
        }
        System.out.print(dividend+"/"+divisor);
    }
}

 

풀이

숫자를 입력받아서 1/1부터 지그재그로 숫자를 읽을 때 입력받은 num번째에 있는 분수를 출력해야 합니다.

일단 지그재그로 읽을 때 첫번째엔 1/1 하나이고 두번째 대각선은 1/2,2/1 이렇게 두개, 세번째 대각선은 3/1,2/2,1/3 이렇게 세개입니다.

이렇게 대각선 하나에 속하는 분수가 한개씩 늘어나므로 한 대각선에 속하는 분수의 개수는 1, 2, 3, 4, 5... 이런식으로 등차수열이 됩니다.

따라서 입력받은수가 14이면 5번째 대각선에 속하며 1+2+3+4+ 4이죠.

그럼 5번째 대각선에 4번째 분수를 출력하게 되면 됩니다.

대각선은 지그재그로 읽기때문에 i번째 대각선은 오른쪽상단부터 내려오면서 읽는지 왼쪽하단부터 올라오면서 읽는지 봐야하는데 i가 짝수이면 위에서 부터 읽고 홀수이면 밑에서 부터 읽습니다.

그래서 if(i%2==0)라는 조건을 걸어주었습니다.

tmp에는 앞에 있는 분수의 개수를 카운트하고 num이 5번째 대각선에 있는 분수라면 num은 1+2+3+4+?일 것이므로 tmp보다는 크고 tmp+i보다는 같거나 작을 것 입니다.

그러니 1~n-1까지의 숫자를 다 더한뒤 num에서 그 수를 빼면 n번째 대각선에 몇번째에 있는지 알 수 있는데 n이 짝수인지 홀수인지 판별하고 짝수이면 분모가 n이고 분자가 1로 시작해서 대각선으로 내려갈수록 분모는 1씩 작아지고 분자는 1씩 커집니다.

홀수이면 그 반대입니다.

이렇게 분모와 분자를 각각 구해서 출력해줍니다.