[백준/Java] 1193. 분수찾기

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

 

🧩  문제 설명

무한히 큰 배열에 다음과 같은 분수들이 있을 때, x(입력값)번째 분수를 구하기

1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> ... 과 같은 지그재그 순서로 1번, 2번, 3번, ... 분수라고 지칭함

---

💡 핵심 아이디어

대각선 방향으로 분수가 나열되는 규칙을 파악하는 것이 핵심

각 대각선에는 분수의 개수가 대각선 번호와 같고,

그 대각선에 속하는 분수들의 분자와 분모의 합은 항상 (대각선 번호 + 1)이 된다

예를 들어,

• 1번째 대각선: 1/1
• 2번째 대각선: 1/2, 2/1
• 3번째 대각선: 3/1, 2/2, 1/3

여기서 규칙은 대각선의 번호에 따라 탐색 순서가 달라진다는 것

---

✅  알고리즘 흐름

1. 대각선 번호 구하기

입력받은 숫자 x번째 분수가 어느 대각선에 있는지 찾기

• 1번째 대각선은 1개, 2번째 대각선은 2개, 3번째는 3개, ..
• 즉, 대각선 d까지의 총 분수 개수는 d(d + 1) / 2 개가 된다
• 이 값이 x보다 크거나 같아지는 최소의 d를 찾으면, 그 대각선에 x번째 분수가 있는 것

2. 대각선 내에서 위치(오프셋) 계산

• x번째 분수가 해당 대각선의 몇 번째에 위치하는지를 구한다
• 바로 이전 대각선까지의 분수 개수는 (d - 1)d / 2 개이므로,
• offset = x - (d - 1)d / 2

3. 대각선 번호에 따른 분자와 분모 결정

• 홀수 대각선일 경우:
  분수는 대각선의 가장 큰 분자부터 시작해서 내려옴
  즉, 분자는 d - offset + 1, 분모는 offset이 된다
  
  
• 짝수 대각선일 경우:
  분수는 작은 분자부터 시작한다
  즉, 분자는 offset, 분모는 d - offset + 1이 된다

4. 예시 (x = 7)

• d를 찾으면:
  1 + 2 + 3 = 6 은 7 보다 작고,
  1 + 2 + 3 + 4 = 10 은 7 보다 크므로 d = 4
  
  
• 오프셋:
  offset = 7 - 6 = 1
  
  
• d = 4는 짝수이므로
  분자 1, 분모 = 4 - 1 + 1 = 4
  
  
• 결과: 1/4

---

✅  풀이 보기 (Java)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int x = Integer.parseInt(br.readLine());
        
        // 대각선 번호 찾기
        int line = 1;
        while (line * (line + 1) / 2 < x) {
            line++;
        }
        
        // 바로 이전 대각선까지의 총 분수 개수
        int prevCount = (line - 1) * line / 2;
        // 현재 대각선에서의 위치
        int offset = x - prevCount;
        
        int numerator, denominator;
        // 짝수 대각선
        if (line % 2 == 0) {
            numerator = offset;
            denominator = line - offset + 1; 
        } else {
            // 홀수
            numerator = line - offset + 1;
            denominator = offset;
        }

        System.out.println(numerator + "/" + denominator);

    }
}