[BAEKJOON] 백준 1193: 분수찾기(C#)

문제 링크

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

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)가 주어진다.

 

출력

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

 

 

통과한 답안

namespace _1193
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int X = int.Parse(Console.ReadLine());

            int n = 0;
            int upper = 0;
            int lower = 0;

            while (Sum(n) < X)
            {
                n++;
            }

            int coeffi = n + 1;

            if (n % 2 == 0)
            {
                upper = X - Sum(n - 1);
                lower = coeffi - upper;
            }
            else
            {
                lower = X - Sum(n - 1);
                upper = coeffi - lower;
            }

            Console.WriteLine(upper + "/" + lower);
        }

        static int Sum(int n)
        {
            return n * (n + 1) / 2;
        }
    }
}

 

이 문제에서 출력해야되는 분수를 적어보면 아래와 같다

(1/1) (1/2, 2/1) (3/1, 2/2, 1/3) (1/4, 2/3, 3/2, 4/1) (5/1, 4/2, 3/3, 2/4, 1/5)

(1/6, 2/5, 3/4, 4/3, 5/2, 6/1) ...

 

출력되는 값들을 분석해보면

 

분모 + 분자가 1, 2, 3, 4, ...으로 늘어난다.

각 묶음은 1개, 2개, 3개, 4개로 분모 + 분자의 값과 같다.

홀수번째 묶음에서는 분자가 최댓값으로 시작하고

짝수번째 묶음에서는 분자가 1부터 시작한다.

 

이들을 가지고 문제를 해결하면,

1. X가 n까지의 합보다 작으면 분모 + 분자는 n + 1이다.

2. n이 짝수면 분자가 1부터 시작하고, n이 홀수면 분모가 1부터 시작한다.

의 두개를 구현하면 된다.

 

while (Sum(n) < X)
{
    n++;
}

static int Sum(int n)
{
    return n * (n + 1) / 2;
}

 

Sum(n) 매소드를 선언한 후에, n을 1부터 증가시키며 X보다 작은 Sum(n)을 찾는다.

 

int coeffi = n + 1;

if (n % 2 == 0)
{
    upper = X - Sum(n - 1);
    lower = coeffi - upper;
}
else
{
    lower = X - Sum(n - 1);
    upper = coeffi - lower;
}

 

coeffi(분모 + 분자)의 값을 n + 1로 설정하고

n이 짝수일 때와 홀수일 때의 분모와 분자를 설정해준다.