[Dev-Ping9] 백준 1193번 - 분수찾기 (Java)

# 문제 설명

• 시간제한이 0.5초 이므로 Brute-Force 한 방법은 통과될 가능성이 낮다.
• 그럼 규칙이 있을테니, 규칙을 찾아본다

 

백준 1193번 분수찾기

 

---

# 규칙

• 대각선을 기준으로 Lv 1 ~ Lv N 이라 정의하면, Lv N 의 원소의 갯수는 N개, 분모와 분자의 합은 N+1 이 된다.

위의 지그재그 배열을 가로로 배열했을 때의 모습 (지그재그아님)

• Lv N의 n번째 원소의 분모는 n이며, 분자는 (N+1) - n 이 된다.
• 하지만, 문제에서 정의된 규칙에 따라 지그재그로 배열을 만들기 때문에 홀수일때와 짝수일때로 경우를 나눠주면 된다.

 

---

# 구현코드 (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    static int reverseIdx =0;
    static int setLevel(int X){
        for(int lv=1;;lv++){
            int boundary = lv*(lv+1)/2;
            if(boundary>=X){
                reverseIdx = boundary-X;
                return lv;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int X = Integer.parseInt(br.readLine());

        // 1 + 2 + 3 + 4 + ...+ n = n(n+1)/2 
        // #sum;  1lv : 2, 2lv :3, 3lv :4, 4lv :5
        // odd -> 0 to n
        // even -> n to 0
        
        int lv = setLevel(X);

        //odd case
        int denominator = lv-reverseIdx; //분모
        int numerator = (lv+1)-denominator; //분자
        
        if(lv%2==1){//odd
            System.out.println((numerator) +"/"+ (denominator));
        }else{//even
            System.out.println((denominator) +"/"+ (numerator));
        }
    }
}