백준 18665번: IQ Test

매일 저녁 6시경에 하루 3백준(≥플레 1문제, 골드 1문제, ≤실버 1문제)을 랜덤으로 뽑아서 풀고 있는데, 보통 플레 이상은 풀 확률이 반반 정도 되는 편.

그 중 간만에 재미있는 문제 하나를 발견해서 기록을 남겨본다.

 

초기 0, 1, 2가 들어있는 집합이 있고 이 집합의 원소 중 x, y 둘을 골라(같아도 됨) $x^2 - y$를 집합에 추가해주는 operation을 가해줄 수 있다. 최대 43번의 operation을 가해서 $10^{18}$까지의 숫자를 만드는 것이 문제의 목표이다.

 

정답은 뭐 크게 어렵지 않고, p를 만들려면 $x^2 \ge p$를 만족하는 가장 작은 x를 찾고, y는 $x^2 - p$를 사용하면 된다. 이후 x, y 만들기를 목표로 이 과정을 반복하면 된다.

 

p의 크기는 최대 $10^{18}$이기에, x의 크기는 최대 $10^9$, y의 경우는 최대 $(10^9)^2 - (10^9 - 1)^2 \approx 2 \times 10^9$ 정도가 된다.

 

결국 대충 뭉뚱그려서,

$10^{18}$ 정도의 숫자 1개 만들기

→ $10^{9}$ 정도의 숫자 2개 만들기

→ $10^{4.5}$ 정도의 숫자 4개 만들기

...

로 계속 문제를 쪼개나갈 수 있는 것이다.

 

일종의 분할 정복인데, 제곱근 형태로 분할되는 것은 처음 보는 것 같아 흥미로운 문제였다.

 

여담으로 제목이 왜 IQ Test인지는 아직도 모르겠다.

 

18665.cpp