[BOJ] 백준 1193 분수찾기

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

 Input 
14

 Output 

2/4

배열에 지그재그로 분수가 주어집니다.

X가 주어질 때, X번째 분수를 구하는 문제입니다.

 

* 10,000,000 숫자를 입력받기 위해 long타입 처리

 

구현

지그재그 순서는 다음과 같습니다.

대각선 한 줄에 위치한 칸의 개수는 등차수열 형태를 가집니다.

▷ 1 + 2 + 3 + 4 + 5 + ...  + (n-1) + n  

[등차수열 공식]

등차 수열 공식을 이용해 x는 몇 번째 대각선에 위치한지 알 수 있습니다.

14 → 5 Line

15 → 5 Line

16 → 6 Line

21 → 6 Line

22 → 7 Line

28 → 7 Line

29 → 8 Line

　

n-th Line이 홀수일 때,

→ 분자는 n부터 감소

→ 분모는 1부터 증가

 

n-th Line이 짝수일 때,

→ 분자는 1부터 증가

→ 분모는 n부터 감소

 

n번째 대각선의 시작지점을 구한 후,

k 번째 위치를 구할 때, 아래 공식 이용.

k = x - ((n-1)*n / 2)

※ 시작지점은 홀수/짝수 대각선에 따라 다릅니다.

홀수/짝수에 따라 분자/분모를 다르게 출력.

- [홀수 일 때] n-k+1 / k

- [짝수 일 때] k / n-k+1

---

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        long x = sc.nextLong();
         
        long n = 1;
        while(true) {
            // 등차수열의 합
            long sum = n * ( n + 1) / 2;
             
            // 등차수열의 합과 주어진 x 비교
            if(x <= sum) {
                break;
            }
            n++;
        }
         
        long k = x - ((n-1) * n / 2);
         
        if(n%2 == 1) { // 홀수 일 때
            System.out.println((n-k+1) + "/" + k);    
        }else {    // 짝수 일 때
            System.out.println(k + "/" + (n-k+1));
        }
    }
}