문제

---

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력

---

첫째 줄에 분수를 출력한다.

풀이

---

몇번째 대각선에 위치하냐에 따라 분모와 분자의 오름차순, 내림차순이 결정된다.

만약 대각선이 홀수에 위치한 경우
분자는 감소하게 되고, 분모는 증가하게 된다.

만약 대각선이 짝수에 위치한 경우
분자는 증가하게 되고, 분모는 증가하게 된다.

그렇다면 몇번째 대각선인지 알아내고 주어진 값에 맞게 분자와 분모를 계산하면 된다.

대각선은 1, 2, 3, 4 개의 숫자를 담을 수 있도록 늘어가고,
주어진 숫자 X가 대각선에 포함되어 있는지를 확인하려면 대각선의 개수를 i라고 할때

X 에 i 를 순차적으로 증가시키며 빼는 것을 반복하다가
만약 X 가 i 보다 작아진다면 i 번째의 대각선의 X 번째에 주어진 숫자가 존재하게 된다.

이후에는 대각선의 홀짝 여부에 따라 분자와 분모를 구하게 된다.

코드

---

#include <iostream>

using namespace std;

int main()
{

    int X;
    cin >> X;

    int i = 1;

    while (X > i)
    {
        X -= i;
        i++;
    }

    if (i % 2 == 0)
        cout << X << "/" << i - X + 1;
    else
        cout << i - X + 1 << "/" << X;

    return 0;
}

리뷰

대각선에 따른 규칙은 찾았지만 주어진 숫자가 어떤 대각선에 포함되는지 구하는
방법이 바로 떠오르지 않아 생각보다 시간이 오래 걸렸다.

주어진 값이 몇번째 공간에 몇번째에 존재하는지 확인하는 방법을 익힐 수 있었다.