[BOJ 1193] 분수찾기 - 수학

문제 링크

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

문제 요약

무한히 큰 배열에 분수들이 지그재그 순서로 나열되어 있을 때, X번째 분수를 찾는 문제

접근 방법

• 자료구조: 변수
• 알고리즘: 수학적 규칙 찾기
• 핵심 아이디어:
  • 대각선 단위로 분수가 나열됨 (n번째 대각선에는 n개의 분수)
  • 홀수 번째 대각선: 분자 감소, 분모 증가 (아래→위)
  • 짝수 번째 대각선: 분자 증가, 분모 감소 (위→아래)
  • n번째 대각선까지 총 분수 개수: 1+2+3+...+n = n(n+1)/2

풀이 과정

1. X번째 분수가 속한 대각선 번호 찾기
   • 1번째 대각선: 1개 (1/1)
   • 2번째 대각선: 2개 (1/2, 2/1)
   • 3번째 대각선: 3개 (3/1, 2/2, 1/3)
2. 해당 대각선 내에서의 위치 계산
3. 대각선 번호의 홀짝에 따라 분자/분모 계산
   • 홀수: numerator = diagonal - position + 1, denominator = position
   • 짝수: numerator = position, denominator = diagonal - position + 1

풀이 코드

#include <iostream>

int main() {
    int x(0);
    std::cin >> x;
    
    // x번째 분수가 속한 대각선 번호 찾기
    int diagonal(1);
    int sum(0);
    
    // diagonal번째 대각선까지의 총 분수 개수가 x 이상이 되는 순간 찾기
    while (sum + diagonal < x) {
        sum += diagonal;
        diagonal++;
    }
    
    // 해당 대각선 내에서의 위치
    int position(x - sum);
    
    int numerator(0);
    int denominator(0);
    
    // 홀수 번째 대각선: 아래에서 위로 (분자 감소, 분모 증가)
    if (diagonal % 2 == 1) {
        numerator = diagonal - position + 1;
        denominator = position;
    }
    // 짝수 번째 대각선: 위에서 아래로 (분자 증가, 분모 감소)
    else {
        numerator = position;
        denominator = diagonal - position + 1;
    }
    
    std::cout << numerator << "/" << denominator << std::endl;
    
    return 0;
}

시간/공간 복잡도

• 시간 복잡도: O(√X) - 대각선 번호를 찾는데 약 √(2X)번 반복
• 공간 복잡도: O(1) - 상수 개의 변수만 사용

실행 결과

• 메모리: 2020 KB
• 시간: 0 ms

핵심 포인트

• 대각선 패턴을 파악하는 것이 핵심
• 등차수열의 합 공식을 이용하면 O(1)로 최적화 가능하지만, 제한 범위 내에서 반복문으로도 충분
• 홀수/짝수 대각선의 진행 방향이 반대임을 주의