[boj] (b1) 1193 분수찾기

1892 단어 bojboj

✅ 구현

문제

링크

풀이

무한히 큰 배열이므로 단순히 이차원 배열에 분수들을 담아놓고 X번째 분수를 찾을 수 없다. 따라서 X값에 따라 분수를 구하는 함수를 구현해야한다.

  1. 지그재그로 이동하므로 X가 몇번째 대각선에 포함되는지에 따라 계산 방식이 다르다. -> X가 몇번째 대각선( i )에 포함되는지 구한다.

  2. 구한 대각선( i )이 홀수인지 짝수인지에 따라 계산 방식을 달리하여 분수를 구한다.

코드

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int X, i, num = 0, a, b; // a: 분자, b: 분모
    cin >> X;

    for (i = 1;; i++)
    {
        num += i;
        if (X <= num)
            break;
    }

    if (i % 2 == 0)
    {
        a = 1;
        b = i;
        for (int j = 0; j < X - (num - (i - 1)); j++)
        {
            a++;
            b--;
        }
    }
    else
    {
        a = i;
        b = 1;
        for (int j = 0; j < X - (num - (i - 1)); j++)
        {
            a--;
            b++;
        }
    }

    cout << a << "/" << b << "\n";

    return 0;
}

좋은 웹페이지 즐겨찾기