문제

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

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

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

입력

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

출력

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

풀이

#include <iostream>

using namespace std;



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

    int N;
    cin >> N;
    int sum = 1; //현재 라인까지의 개수
    int plus = 1; //라인이 증가할 때마다 더해줄 수 
    int line = 1; //라인 번호
    while (N > sum) {
        plus++;
        sum += plus;
        line++;
    }
    int numerator; //분자
    int denominator; //분모
    numerator = line - (sum - N);
    denominator = (line + 1) - numerator;

    //지그재그이기 때문에 홀수 라인의 경우 분자 분모를 바꾼다.
    if (line % 2 == 1) {
        int tmp = numerator;
        numerator = denominator;
        denominator = tmp;
    }

    cout << numerator << '/' << denominator << '\n';


    return 0;
}

이 문제는 대각선으로 라인을 그려서 해석하였다.

1. 입력된 번호가 어떤 라인에 있는지 찾기위해서 라인의 가장 큰 숫자를 통해서 그보다 클동안 라인을 하나씩 올려주어 해당 라인을 찾는다.
2. 지그재그가 아닌 오른쪽 위부터 시작한다는 가정으로 우선 생각하여 분모와 분자를 정해준다.
3. 지그재그로 숫자가 매겨지기 때문에 홀수의 경우 왼쪽 아래부터 시작하여 분자와 분모 값을 바꿔준다.
4. 분자와 분모를 출력한다.