[1193] 분수찾기

🍃 문제

1193번: 분수찾기

 

수2였나.... 수열을 배우는 단원에서 군수열이라는 개념이 나온다.

학회 면접을 볼 때도 이 문제가 나왔었는데 그때는 시간이 촉박한 탓에 당황하여 코드는 작성하지 못했고

시간을 더 줄테니 어떻게 해결하면 좋을지 말해보라고 하셨다ㅎㅎㅎ

면접관들은 나만 보고 계시고... 코드로는 어떻게 해야할지 빨리빨리 생각나지도 않고... 그래서

"저 혹시.. 군수열이라고 아시나요...? 고등학교때 배웠던건데 어쩌고 저쩌고...." 하면서 횡설수설하고 온 기억이 있다.

쨌든 합격~!

 

 

🍃 해결 방법

문제에서 말하는 조건을 군수열 로 나타내면 아래의 그림과 같다.

이때 자세히 보면 홀수군은 분모가 증가하고 분자가 감소하지만

짝수군은 분모가 감소하고 분자가 증가하는 것을 알 수 있다.

따라서 내가 찾고자하는 번째의 수가 몇 군에 있는지를 알기 위해서

if ((1 + i * (i - 1) / 2 <= x) && (x < 1 + i * (i + 1) / 2))​

위와 같은 if문을 작성해주었다.

'1 + i * (i - 1) / 2' 은 각 군의 첫 번째 인덱스를 나타내는 것이고,

'1 + i * (i + 1) / 2' 은 그 다음 군의 첫 번째 인덱스를 뜻한다.

이 식은

1 = 1군

2 ~ 3 = 2군

4 ~ 6 = 3군

7 ~ 10 = 4군

....

인 것을 활용하여 계차수열을 통해 구할 수 있다.

그리고 정답은 소수가 아닌 분수로 나타내어야 하기 때문에 출력 형태는 분자 + '/' + 분모 꼴로 해야한다.

따라서 분자와 분모를 각각 구해주어야 하는데

예를 들어, 9번째 분수를 찾고 싶다고 가정하자.

그 수는 4군에 있고,

분자는 1에다가 자신과 4군의 첫번째 인덱스 차이 만큼을 더한 숫자이고,

분모는 다음 군, 즉 5군의 첫번째 인덱스와 자신과의 차이가 된다. 그림을 통해 더 자세하게 이해하자!

홀수군일 때는 짝수군일 때와 분모, 분자식만 뒤바꿔주면 된다. 끝!

 

 

🍃 내 코드(C++)

// [1193] 분수찾기
// https://www.acmicpc.net/problem/1193

#include <iostream>
using namespace std;

int main(void)
{
    int x, denominator, numerator;
    cin >> x;
    for (int i = 1;; i++) {
        if ((1 + i*(i - 1) / 2 <= x) && (x < 1 + i*(i + 1) / 2)) {

            // 짝수 군
            if (i % 2 == 0) {
                numerator = 1 + x - (1 + i * (i - 1) / 2); // 분자
                denominator = 1 + i * (i + 1) / 2 - x; // 분모
            }

            // 홀수 군
            else {
                numerator = 1 + i * (i + 1) / 2 - x;
                denominator = 1 + x - (1 + i * (i - 1) / 2);
            }

            break;
        }
    }

    cout << numerator << "/" << denominator << endl;
}