[SWEA - 9843]촛불 이벤트

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXGBKzuaPOoDFAXR

SW Expert Academy

일단, 테스트 케이스의 개수 + 제공되는 변수의 범위를 생각해보면

선형탐색으로는 절대 절대 풀수 없는 문제다.

이럴때 풀라고 있는게 이분 탐색이 아닐까?

 

어찌돼었든,

문제를 풀때 수학적인 요소가 있긴하지만 그리 강하지는 않다.

가우스 합 공식

이 식을 잘 생각해보자.

입력하는 값 N에 따라, x의 값을 구하는 것이 이 문제의 핵심적인 요소다.

여기까지만 본다면, x를 1부터 쭉 구해서 N과 같아질때 까지 선형 탐색을 하는방법을 생각해볼수 있다.

하지만, 이런 선형탐색 방식을 사용한다면, 최악의 경우 10의 18승까지 쭉 탐색을하게될것이고, 쓸데없는 자원낭비가 될것이다.

그렇다면 여기서 사용해야할 방식은 무엇일까?

바로 이분 탐색 일것이다. 먼저 x의 최대 범위를 N이들어오는 2N까지 끌어올려서

0 ~ 2N의 범위에서 탐색할수 있겠으나

이는 long long 을 차용하더라도, x^2에서 연산범위를 초과해 이분탐색을 할수 없게 만든다.

다시한번 수식을 정리해 보자.

대략 이러한 형태가 될것이다.

여기서 정확한 x의 수치를 구하는것보다 대략적인 감만 보자.

x는 무조건 1보다 클것이기 때문에 x를 뺐을 경우, 우변이 좌변보다 크게되는 비교식을 얻을수 있다.

그렇다면 다시한번 수식을 정리해보면

이러한 식을 얻게 된다.

여기서 앞전 지웠던 +x에 대한 값을 감안해보았을때, 대략 추정범위는 우변과 같다고생각했고

끝범위를 우변과같이 설정해서 답을 도출할수 있었다.