백준 1193_분수찾기[C++]

문제

 

풀이

 이 문제는 저도 이해하고 규칙을 찾는데 꽤 오랜 시간이 걸리는 문제였습니다. 먼저 문제에서 1/1->1/2->2/1->3/1->2/2->1/3->1/4 ... 이런식으로 분모와 분자가 대각선 방향으로 반대로 커지거나 작아지며, 작아지다가 1/n 또는 n/1이 되면 n+1을 해주고 위의 과정을 반복하는 방식으로 배열이 구성되어 있습니다. 

위 설명에서 대각선에 대한 규칙이 있습니다. 대각선이 홀수인 경우에는 분자가 증가하고, 반대로 짝수인 경우에는 분모가 증가한다는 것입니다. 따라서 분자가 구해지면 분모는 (대각선의 단계-분자 수+1)의 공식이 성립하게 됩니다 (반대로 분모를 먼저 구하는 경우에도 마찬가지입니다). 이 공식을 활용하여 소스코드를 작성하면 다음과 같습니다.

 

 

소스코드

#include<iostream>
using namespace std;


int main(){
 long long n, step=1;
 long long a=0,b=0;
 cin >>n;
 if (n==1) {
     cout << "1/1";
     return 0;
 }
 while(n-step>0){
     n-=step;
     step++;
 }

 if(step%2==0) {
     cout << n <<"/" << step-n+1;
 }else{
     cout <<step-n+1<<"/"<<n;
 }
}