[BAEKJOON] 백준 15667: 2018 연세대학교 프로그래밍 경진대회 (C#)

문제 링크

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

 

 

문제

2015, 2016, 2017년에 이어 올해도 연세대학교 컴퓨터과학과 프로그래밍 경진대회가 열린다.

도현이는 4년 연속 교내대회가 개최된다는 것에 감격하여, 사비를 털 각오로 화려한 개막식을 준비했다.

도현이가 원하는 것은 폭죽으로, 강의실 A528에서 천장을 다 뚫어버리며 터지는 화려한 폭죽을 모두가 좋아할 것이라 생각했다. 도현이는 아래와 같이 터지는 폭죽을 주문하려 한다.

1. 처음 발사된 폭죽이 만든 하나의 대형 불꽃은 적당한 높이에 도달하면 화려한 폭발과 함께 K개의 중형 불꽃으로 갈라진다.
2. 각 K개의 중형 불꽃은 다시 각각 K개의 소형 불꽃으로 갈라지며 터진다.
3. 그 이후 모든 불꽃은 소멸한다.

도현이는 적당한 폭죽을 찾아보려 했지만, 폭죽 판매처에서는 K의 값을 알려주지 않았고,

대신 폭죽 하나당 만들어지는 총 불꽃의 수(처음 터진 대형 불꽃을 포함해, 중형 불꽃과 소형 불꽃을 모두 포함한 수)만을 알려줬다. 결국 도현이는 어떤 폭죽이 적당할지 알아내지 못해 폭죽을 구매하지 못했다.

이에 도현이는 이 난제를 해결해주는 학생에게 이번 대회에서 맞은 문제 수를 하나 늘려주기로 하였다. 여러분은 대회에서 우승하기 위해, 폭죽이 만들 모든 불꽃의 개수가 주어지면 K의 값을 찾아보도록 하자.

 

 

입력

총 불꽃의 수 N이 주어진다. (3 ≤ N ≤ 10101)

 

 

출력

K의 값을 출력한다. 이 값은 정수임이 보장되며, 불가능한 경우는 입력으로 주어지지 않는다.

 

 

 

통과한 답안

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

            int left = 0;
            int right = n;
            int result = -1;

            while (left <= right)
            {
                int mid = left + (right - left) / 2;
                long value = (long)mid * mid + mid + 1;

                if (value == n)
                {
                    result = mid;
                    break;
                }
                else if (value < n)
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }

            Console.WriteLine(result);
        }
    }
}

 

하나의 폭죽이 터져서 K개의 중형 불꽃으로 갈라지고,

중형 불꽃이 터져서 각각 K개의 소형 불꽃으로 갈라지는 조건이 주어졌다.

이 경우에 총 불꽃의 개수가 주어졌을 때, K를 구하는 문제이다.

 

하나의 폭죽이 1번 터져서 K개가 되고,

K개의 중형 불꽃이 각각 K개가 되므로 총 K^2개의 불꽃이 된다.

즉, 하나의 폭죽이 터지면 K^2 + K + 1의 불꽃이 생긴다.

 

따라서 K^2 + K + 1 = n이라는 조건을 만족시키는 K값을 구하는 문제이다.

이를 아래의 근의 공식을 이용해서

a = 1, b = 1, c = 1 - n 이므로

 

k = (-1 + 루트(4n - 3)) / 2를 이용해서 구할 수 있다.

 

하지만 루트를 이용하기도 하고 단순히 근의 공식을 이용해서 풀이하는 것보다

프로그래밍 기술을 이용해서 풀이하려고 찾다가 이분 탐색을 이용해서 풀 수도 있는 것을 발견했다.

 

left를 0, right를 n으로 설정한 뒤에

주어진 조건 (K^2 + K + 1 = n)을 만족하는 K를 구하는 방식으로 이분 탐색을 구현하였다.