[1193번] 분수찾기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 규칙 찾기

2. 일반항 구하기(계차수열)

아래 그림을 자세히 보면

1/1을 기준으로 ↘ 방향으로 보면 항상 규칙이 있다.

1 + 2n(n-1)번째에 항상 값이 존재한다.

예를들어 2/2는 1 + 2*2(1) 즉, 처음부터 시작하면 5번만에 도착할 수 있다.

이러한 방식으로 k번째 값이 무엇인지 궁금할 때

k보다 크거나 같은 값을 구해서 그 값을 기준으로 역행하면 답을 찾을 수 있다.

물론 이렇게 하면 조금 더 빠를것이다.

k보다 크거나 같고 k보다 작거나 같은 값을 구해서 그 두 값중 k가 가까운 쪽의 값을 선택하여 그 부분부터 k를 찾아간다면

좀 더 빠를것이다.

소스 코드 : 

#include <iostream>
 
using namespace std;
 
int main()
{
    int n;
    int ans;
    int bunmo = 0, bunja = 0;
    int flag = 0;
 
    cin >> n;
 
    for (int i = 1;; i++)
    {
        if (n <= 1 + 2 * i*(i - 1))
        {
            ans = i;
            break;
        }
    }
 
    // 분자 분모 초기화
    bunmo = ans;
    bunja = ans;
 
    // 지금부터 ans에는 
    // 현재 분수에 해당하는 번호가 들어간다
    ans = 1 + 2 * ans*(ans - 1);
 
    while (1)
    {
        // ans가 n을 찾아갔을 때
        if (n == ans)
            break;
 
        // 역순회해야 하니 왼쪽밑으로 먼저 돈다.
        if(flag == 0)
        {
            if (bunmo == 1)
            {    
                bunja--;
                flag = 1;
            }
            else
            {
                bunmo--;
                bunja++;
            }
        }
 
        else if (flag == 1)
        {
            if (bunja == 1)
            {
                bunmo--;
                flag = 0;
            }
            else
            {
                bunmo++;
                bunja--;
            }
        }
        ans--;
    }
    cout << bunja << "/" << bunmo;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>