[C#] 백준 1011번 Fly me to the Alpha Centauri

문제

정답 코드 :

using System;

namespace _9
{
    class Program
    {
        static void Main(string[] args)
        {
            int T = Convert.ToInt32(Console.ReadLine());
            for (int i = 0; i < T; i++)
            {
                string input = Console.ReadLine();
                string[] inputData = input.Split(' ');
                long x = Convert.ToInt32(inputData[0].ToString());
                long y = Convert.ToInt32(inputData[1].ToString());

                long an = 2;
                long k = 2;
                long d = y - x;
                long count = 1;
                long output = 0;
                while (d > an)
                {
                    an += 2 * k;
                    k += 1;
                    count += 1;
                }

                if (an - count < d)
                    output = count * 2;
                else
                    output = (count * 2) - 1;

                Console.WriteLine(output);
            }
        }
    }
}

문제를 손으로 직접 풀다보면

이런식이다. 정리를 해보면

1번으로 가는게 1개, 2번으로 가는게 1개, 3번으로 가는게 2개, 4번으로 가는게 2개 등등 2번씩 쌍으로 늘어남을 알 수 있다. 끝 수인 2, 6, 12, 20을 수열로 만들면 첫항이 2인 계차수열이 만들어진다. 그렇게 되면 예를 들어 an = 6이면 3번 혹은 4번 둘중에 하나라고 할 수 있다.

if (an - count < d)
	output = count * 2;
else
	output = (count * 2) - 1;

d가 3이면 an이 6일때 걸린데 그때 count는 2이다. 즉 6-2 < 3 이므로 output = 2 * 2 -1, 즉 3이 된다.

이렇듯 수학문제는 규칙을 찾는것이 가장 중요하다. 이 문제의 포인트는 하나씩 더해가는 코드를 짜는것보단 수기로 풀어보면서 규칙을 찾고 수식화해서 얼마나 간결하게 만드는것이냐가 중요하다고 생각한다.