백준 1193 - 분수찾기

문제설명

 

 

=> 단순한 규칙성을 찾는 문제입니다. 

=> 처음부터 끝까지 찾아갈 경우 시간제한에 걸리는 경우가 생길 수 있습니다. 

 

 

 

 

• x가 몇번째 줄에 해당하는지 찾습니다. 
• 해당 줄이 짝수인지 홀수인지 판별합니다.
• 각 줄의 성질에 따라 deno(분모), nume(분자)를 구하여 print 합니다. 
• 각 줄에 있는 분수는 아래의 성질을 만족합니다. 
• line + 1 = 분모 + 분자
• 위의 성질을 이용하여 for문을 통한 탐색이 아닌 사칙연산으로 원하는 분수를 구할 수 있습니다. 

규칙을 찾기 위해 써본 노트

 

 

 

#include <iostream>
#include <algorithm>

using namespace std;

void Print(int deno, int nume)
{
    cout<<nume<<'/'<<deno<<'\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int deno, nume;//분모, 분자 변수 설정
    deno = 1;
    nume = 1;
    
    int x;
    cin >> x;
    
    if(x == 1) // 첫번째인 경우
    {
        Print(deno, nume);
    }
    else// 순서를 찾아야하는 경우
    {
        deno++; //분모 2로 설정
        int line = 2; //줄 횟수
        int minus =2;
        while(1)
        {
            if(x - (minus+1) >0) //더아래로 내려갈수 있는 경우
            {
                x -= minus++;
                line++;
            }
            else //줄이 해당 줄인 경우
            {
                break;
            }
            
        }
        //cout << line ;
        if(line % 2 == 0) //짝수행일때
        {
            deno =line - (x-2);
            nume =(line+1) - deno;
            Print(deno, nume);
        }
        else//홀수행일때
        {
            nume =line - (x-2);
            deno = (line+1) - nume;
            Print(deno, nume);
        }
    }
    return 0;
}

 

 

 

실행 화면

실행 화면2