[BOJ/백준/C++] 1193번 분수찾기

1193번: 분수찾기

---

반응형

📌 접근 방법

• 분수 표를 비스듬히 두고보면 첫 번째 줄에는 1개의 분수가, 2번째 줄에는 2개의 분수가 3번째 줄에는 3개의 분수가 있는 것을 볼 수 있다.
• 규칙 : 입력받은 x는 1부터 r-1까지의 합과 1부터 r까지의 합 사이에 위치한다
  ➡ (r-1)*r/2 < x ≤ r *(r+1)/2 (합 구하는 공식)
  ➡ 해당 x가 몇 번째 줄에 위치하는지 알 수 있다.
• 분수의 분자, 분모의 합은 해당 줄에서 1을 더한 값으로 일정하다.
• 짝수 줄에는 분모가 r에서 1로 하나씩 줄어들고 분자는 반대로 1에서 r로 늘어난다.
• 홀수 줄은 그와 반대로 작용한다.

 

✅ Pass Code

#include<iostream>
#include<string>
#include<cmath>
using namespace std;

int main()
{
    int x;
    cin>>x;
    int r=1; //수열의 줄
    //1~r-1의 합<x<=1~r의 합

    while(true){
        if(r*(r+1)/2>=x)break;
        r++;
    }
    //분모 분자의 합이 r(줄)+1임
    //홀수 줄은 분자가 r에서 1로 줄어들고 분모는 1에서 r로 늘어남
    //짝수는 그 반대
    int a = (r-1)*r/2;
    int i = x-a;
    int j = r+1-i;
    if(r%2!=0){
        cout<<j<<"/"<<i<<endl;
    }
    else{
        cout<<i<<"/"<<j<<endl;
    }
    return 0;
}