BOJ 15719 - 중복된 숫자

링크: https://www.acmicpc.net/problem/15719

문제

자료형의 비트를 이용하여 배열을 압축하여 사용하는 방법과, 수학으로 푸는 2가지 풀이를 소개하려 한다.

풀이 1 (비트)

표현할 정수의 범위는 [0, 10000000]이다. 그리고 필요한 정보는 각 숫자들이 사용되었는가/아닌가 이다.

사용되지 않았다면 0, 사용되었다면 1로 표현한다면 숫자 하나의 사용 여부를 하나의 비트로 관리할 수 있다.
즉, 32비트 정수 하나에 32개의 수의 상태를 담을 수 있다.

그럼 배열의 크기는 \(\lceil 10~000~000 / 32 \rceil = 312~500\)만큼 필요하다. 코드는 훨씬 간단하다.

코드

풀이 2 (수학)

1부터 \(n-1\)까지의 수가 골고루 등장한다. 등장한 모든 수의 합을 \(S\), 한번 더 등장한 어떤 수를 \(m\)이라고 하자. 그럼 다음 식을 만족한다.
$$ S = \frac{n(n-1)}{2} + m $$

\(n \le 10,000,000\) 이므로 \(n(n-1)\)도 long long형으로 커버가 가능하므로 구현이 쉽다.

코드