백준 1193번 분수찾기

문제 링크입니다: https://www.acmicpc.net/problem/1193

그림을 통해 간단히 설명하겠습니다.

우선 찾을 순서는 위와 같이 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> 1/3 -> ... 순입니다.

오른쪽으로 갈수록 대각선의 길이가 1씩 증가하는 것을 확인할 수 있습니다.(1, 2, 3, 4, 5, ...)

또한, 빨간색 대각선을 보면 대각선마다 (분모 + 분자)가 동일한 것을 확인할 수 있습니다.(2, 3, 4, 5, 6, ...)

따라서, X번째 분수가 어디 대각선에 속하는지 그리고 해당 대각선의 합이 몇인지를 알고 나면 쉽게 풀 수 있는 문제였습니다.

#include <iostream>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int X;

        cin >> X;

 

        //1일 경우

        if (X == 1)

        {

                 cout << 1 << "/" << 1 << "\n";

                 return 0;

        }

 

        int sum = 1; //대각선에 속한 분수들의 분모 + 분자

        long long cnt = 0; //몇 번째?

        int num = 1;

        while (1)

        {

                 sum++;

                 cnt += num;

                 if (cnt >= X)

                         break;

 

                 num++;

        }

 

        int child = 1, parent = 1;

        if (sum % 2)

                 child = sum - 1;

        else

                 parent = sum - 1;

 

        while (1)

        {

                 if (cnt == X)

                         break;

 

                 if (sum % 2)

                 {

                         parent++;

                         child--;

                 }

                 else

                 {

                         child++;

                         parent--;

                 }

                 cnt--;

        }

        cout << child << "/" << parent << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~