링크: https://www.acmicpc.net/problem/13701문제BOJ 15719 - 중복된 숫자를 비트로 해결하는 풀이와 같다. 엄밀히 말하면 이 문제가 더 먼저 만들어졌다.정확히 같은 풀이이므로 링크로 대체한다.다른 점이 있다면, 표현할 수의 범위가 \(2^{25}\)가 최대이므로 32비트 정수 배열의 크기가 \(2^{25}~/~32=1~048~576\)이면 된다.코드

링크: 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..