[백준] 1193번: 분수찾기

https://www.acmicpc.net/problem/1193

1193번: 분수찾기

문제 이해

역시 문제를 이해하는 것이 중요하다

문제에서 제시한 표가 2차원 배열로 주어져서 그런데, 그냥 수의 나열로 보는게 훨씬 낫다.

분자와 분모의 합이 2인 것은 1개

분자와 분모의 합이 3인 것은 2개

분자와 분모의 합이 4인 것은 3개 

이런 식으로 이어진다. 

 

이걸 일반화하면 분자와 분모의 합이 i+1 인 것이 i개씩 나열되어 있는 것이다. 

 

각 덩어리를 살펴보면 

i가 홀수인 경우에는 분자가 큰 경우부터 나열되고

i가 짝수인 경우에는 분자가 작은 경우부터 나열된다.

 

다시 일반화 하면

i가 홀수인 경우 분모가 1부터 i-1까지 늘어나고, 분자는 i-1부터 1까지 줄어든다.

i가 짝수인 경우 분모가 i-1부터 1까지 줄어들고, 분자는 1부터 i-1까지 늘어난다.

 

그럼, N이 주어졌을 때, 이 N이 어느 덩어리에 속해있는지를 찾아서, 덩어리 중 몇 번째인지를 알아내면 된다.

작성 코드

#include <iostream>

using namespace std;

int X;

int main(void){
    
    // 변수
    int cnt = 0;
    int idx;

    // 입력 받기
    cin >> X;
    
    // 해당 숫자의 위치 찾기
    for(int i = 1; ;i++){
        //i단계의 요소 i개 만큼 있음 -> 이 분수의 분자+분모 == i+1
        cnt += i;
        if(cnt >= X){
            // i번째 묶음에 존재
            cnt-=i;
            idx = X-cnt; // 묶음 중 몇 번째인지
            if(i%2 == 0) printf("%d/%d", idx, (i+1)-idx); // 짝수인 경우
            else printf("%d/%d", (i+1)-idx, idx);		// 홀수인 경우
            return 0;
        }
    }
    return 0;
}