[백준] 1193 분수찾기 [자바]

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

 

문제

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

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력

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

풀이

이 표의 순서는 이렇게 진행된다.

그룹으로 나누어 생각해 보자.
화살표 기준으로
1그룹: 1/1
2그룹: 1/2 2/1
3그룹: 3/1 2/2 1/3
4그룹: 1/ 2/3 3/2/ 4/1

홀수 그룹은 분자가 감소하고 분모가 증가하고
짝수 그룹은 분자가 증가하고 분모가 감소한다.

따라서

import java.util.Scanner;

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

        int X = sc.nextInt();
        int n=0;
        int top=1;
        int bot=1;
        int cnt=0;
        if(X==1) {
            System.out.println("1/1");
        }else {
            while(cnt<X){
                n++;
                cnt=n*(n+1)/2; //몇번 째 행인지 찾는 코드
            }
            int num=X-(n-1)*n/2;  //행의 몇번 째 값인지 찾는 코드
            if(n%2==0) {  //짝수 행일 시
                top=num;
                bot=n-num+1;
            }else {
                top=n-num+1;
                bot=num;
            }
            System.out.println(top+"/"+bot);
        }

    }
}