Sqrt Decomposition

1. 합이 N인 수들 중 서로 다른 수들의 개수는 최대 $O(\sqrt{N})$개 이다.

서로 다른 수들을 최대한 많이 만들기 위해서는, 모든 수들이 서로 다르고, 1, 2, ... 와 같이 1부터 하나씩 채워 나가는 것이다.

$1+2+...+x=N$이니, $x<=\sqrt{N}$이다.

압축을 통해 보아야 하는 서로 다른 수들의 위치를 $O(\sqrt{N})$개로 줄일 수 있다.

 

2. 합이 N인 수들 중 $\sqrt{N}$ 이상의 수들의 최대 개수는 $O(\sqrt{N})$개 이다.

$\sqrt{N} \cdot \sqrt{N}>=N$이니, $\sqrt{N}$ 이상의 수들은 많아봤자 $O(\sqrt{N})$개가 된다.

$\sqrt{N}$ 이상과 이하인 수들로 나누어 $\sqrt{N}$ 이상인 수들은 그 개수가 $\sqrt{N}$개 이하임을 이용하고, $\sqrt{N}$ 이하인 수들은 그 크기가 $\sqrt{N}$이하임을 이용하여 서로 다른 방법으로 해결할 수 있다.