백준 1193 : 분수찾기

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

1/1	1/2	1/3	1/4	1/5	…
2/1	2/2	2/3	2/4	…	…
3/1	3/2	3/3	…	…	…
4/1	4/2	…	…	…	…
5/1	…	…	…	…	…
…	…	…	…	…	…

이와 같이 나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

첫째 줄에 분수를 출력한다.

:: 성공

 

: 설명 :

> 속도가 중요함 = 공식을 써서 풀라는 것...

 

> 각 단계마다 +1씩 개수들이 증가한다.

>> 1단계(1/1) 2단계(1/2, 2/1) 3단계(3/1, 2/2, 1/3)

 

> 그러니 우선 받은 숫자가 몇 단계 다음인지를 확인한다.

>> 14의 경우 5단계 다음에 온다.

 

> 그 후 다음 단계 가장 처음에 오는 숫자의 번째를 확인(5단계 다음 시작은 11번째부터).

> 지금 받은 숫자가 5단계 다음 시작해서 몇 번째에 오는지 확인(11번째부터 14번째까지니까 6단계 시작해서 4번째, 차이는 3)

> 그 다음은 홀수 짝수를 구분해서 분수를 보여주면 된다.

>> 5단계는 홀수,

>>> 그러니 시작은 5/1 거기서 차이(3)만큼 위는 빼고, 아래는 더한다.

>>> 나오는 것은 2/4

 

: 개선점 : 수학에 대한 이해

using System;

namespace Math00
{
    class Program
    {
        static void Main(string[] args)
        {
            // :: Read
            string input = Console.ReadLine();

            // :: Set
            int checkNumber = int.Parse(input);

            // :: Find
            int count = 1;
            int range = 1;
            int firstNumber = 1;
            while(true)
            {
                // ::: EXIT
                if (checkNumber <= range)
                    break;

                count += 1;
                firstNumber = range + 1;
                range += count;
            }

            // :: Get
            int up = 1;
            int down = 1;
            if(count % 2 == 1)
            {
                up = count - (checkNumber - firstNumber);
                down = 1 + (checkNumber - firstNumber);
            } else if(count % 2 == 0)
            {
                up = 1 + (checkNumber - firstNumber);
                down = count - (checkNumber - firstNumber);
            }

            // :: Print
            string print = string.Format("{0}/{1}", up, down);
            Console.WriteLine(print);
        }
    }
}