[백준] 1193번 : 분수찾기

 

 풀고 보니 발상이 실버 문제라고 하여 실버 등급이 매겨져 있다. 가장 기본적인 아이디어는 군수열이라고 하던데 나는 군수열에 대해 배운 적이 없다..

 

 인터넷에 찾아보니 군수열의 정확한 정의는 어디에도 없다.. 그냥 내 방식대로 얄팍하게 정의해 보자면, 수열을 규칙에 따라 여러 개의 군으로 묶은 것이라고 할 수 있겠다.

 

 이 문제를 예로 들어보자. 분자와 분모의 합을 기준으로 나열된 분수들을 군으로 묶는다면 (2), (3, 3), (4, 4, 4), ... 과 같이 나타낼 수 있다.

 

 일단 코드부터 확인해 보자.

#include <iostream>
using namespace std;

int main()
{
    int X;
    cin >> X;

    int numer = 1, denom = 1;
    bool upperDirection = true;
    for (int count = 1; count < X; count++)
    {
        if (upperDirection == true)
        {
            numer--;
            denom++;
        }
        else
        {
            numer++;
            denom--;
        }

        if (numer == 0)
        {
            upperDirection = !upperDirection;
            numer++;
        }
        else if (denom == 0)
        {
            upperDirection = !upperDirection;
            denom++;
        }
    }

    cout << numer << "/" << denom;

    return 0;
}

 이 문제에 대한 나의 아이디어를 이미지 한 장으로 요약해 보겠다.

 

 위의 코드에서 upperDirection이라는 flag를 사용하였는데, upperDirection이 참일 때는 우측 상단을 가리키는 대각선, 거짓일 때는 좌측 하단을 가리키는 대각선이다. 내가 고안한 알고리즘은 다음과 같다.

---

1. 위에서 이 분수들을 분자와 분모의 합을 기준으로 군으로 묶은 바 있는데, 첫 번째 군은 upperDirection으로 취급한다.
2. upperDirection 값에 따라 분자(numer, numerator)와 분모(denom, denominator)의 값을 조정한다.
   1. upperDirection이 참이면 이번 iteration에서 분자는 감소, 분모는 증가한다.
   2. upperDirection이 거짓이면 이번 iteration에서 분자는 증가, 분모는 감소한다.
3. 분자나 분모의 값이 0에 도달하면 0에 도달한 값만 다시 1로 올려주고, upperDirection flag를 반대로 바꾼다. 위 그림에서 각각의 화살표가 방향의 끝에 도달했을 때 수행되는 작업을 구현한 것이다. 첫 번째 분수 1/1은 upperDirection이 참이므로 0/2이 되고 flag가 반대로 바뀌면서 분자만 증가해 1/2로 바뀐다. 그리고 그건 두 번째 분수이다. 세 번째 분수 2/1은 upperDirection이 거짓이므로 3/0이 되고 flag가 반대로 바뀌면서 분모만 증가해 3/1이 된다. 그리고 그건 네 번째 분수이다.
4. 2~3의 과정을 X - 1회 반복한다.
   1. X가 1일 때, numer과 denom은 이미 기본값이 첫 번째 분수를 나타내므로 0회의 반복으로 성립한다.
   2. 첫 번째 분수인 상태에서 1회 반복할 때마다 다음 순서의 원소로 바뀌는 것이므로 X번째 분수가 되려면 X - 1번의 반복이 필요하다.

---

 처음에는 군의 분수 개수가 1, 2, 3, ... 개이고 분수의 분자와 분모의 합은 2, 3, 4, ... 이므로, 이 규칙성을 이용해 처음 입력받는 수 X가 9라고 가정하면

1. 1부터 어떤 수 k까지의 합이 9 이하가 되는 k의 최댓값을 구한다.
2. k + 1은 해당 군에 속하는 분수들의 분자와 분모의 합이다.
3. k번째 분수를 초기값으로 설정, X - k회 만큼 반복하면서 k % 2의 값에 따라(upperDirection flag와 똑같이 작동) numer, denom의 값을 조정한다.

와 같이 풀려고 했으나 코드가 너무 지저분해져서 위와 같이 해결했다.