BOJ 1193 - 분수찾기

문제

분수를 대각선 지그재그 순서로 나열할 때, X번째 분수를 구하라. 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → 1/3 → ...

입력

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

출력

X번째 분수를 출력한다.

예제

입력	출력
`14`	`2/4`

풀이

대각선 번호(cnt)를 증가시키며 X가 속한 대각선을 찾고, 대각선 내 위치로 분수를 결정한다.

cnt번째 대각선에는 cnt개의 분수가 있다. 누적합(sum)이 X 이상이 될 때까지 cnt를 증가시킨다
X가 속한 대각선에서의 위치: pos = X - sum (1-indexed)
홀수 대각선: 분자가 감소, 분모가 증가 → (cnt - pos + 1) / pos
짝수 대각선: 분자가 증가, 분모가 감소 → pos / (cnt - pos + 1)

핵심 아이디어: 대각선 번호가 홀수/짝수인지에 따라 분자-분모의 순서가 반대이며, 대각선 내 위치로 분자와 분모를 직접 계산한다.

코드

package day449;
 
import java.io.*;
 
public class Day406BOJ1193분수찾기 {
  static int X, cnt = 1, sum = 0;
 
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    X = Integer.parseInt(br.readLine());
 
    while (true) {
      if (X <= sum + cnt) {
 
        if (cnt % 2 == 1) {
          System.out.print((cnt - (X - sum - 1)) + "/" + (X - sum));
          break;
        }
 
        else {
          System.out.print((X - sum) + "/" + (cnt - (X - sum - 1)));
          break;
        }
 
      } else {
        sum += cnt;
        cnt++;
      }
    }
  }
}

복잡도

시간: O(sqrt(X)) (대각선 번호가 sqrt(2X)에 비례)
공간: O(1)

문제