[BOJ 24500] 백준 24500번 - blobblush

		제 1회 블롭컵 풀이
A		[BOJ 24498] blobnom
B		[BOJ 24499] blobyum
C		[BOJ 24500] blobblush

1. 문제

$24500$. blobblush (제1회 블롭컵 C번)

백준 24500번 - blobblush (https://www.acmicpc.net/problem/24500)

2. 풀이

$1$부터 $N$까지의 수 중에 적절히 뽑아서 만든 배타적 논리합의 최댓값은 $N$이상인 $N$과 가장 가까운 $2$의 승수임을 알 수 있다. Bitwise XOR연산은 해당 자리 숫자를 $0$이나 $1$로 만들 뿐, 자릿수를 늘릴 수는 없기 때문이다.

목표 수를 알게 되었으니 $N$에서 해당 수를 만들기 위해 필요한 카드들을 최소 개수로 생각해본다. 그럼 다음과 같이 표로 정리할 수 있다.

N	카드	XOR	개수
1(1)	1(1)	1(1)	1
2(10)	1(1) 2(10)	3(11)	2
3(11)	3(11)	3(11)	1
4(100)	3(11) 4(100)	7(111)	2
5(101)	2(10) 5(101)	7(111)	2
6(110)	1(1) 6(110)	7(111)	2
7(111)	7(111)	7(111)	1
8(1000)	7(111) 8(1000)	15(1111)	2
9(1001)	6(110) 9(1001)	15(1111)	2
10(1010)	5(101) 10(1010)	15(1111)	2

이를 통해 $1$개 또는 $2$개를 사용하여 목표를 만들 수 있음을 알 수 있고, $1$개가 필요한 경우는 그 자체로 $(2의\,승수 - 1)$일 때라는 사실도 알 수 있다.

따라서, $N$이 $(2의\,승수 - 1)$이면 개수 $1$과 본인을 출력하면 되고, $N$이 그 이외의 수이면 개수 $2$와 $(목표 수)$, $(N - 목표 수)$ 두 개의 수를 출력하면 된다.

3. 채점 결과

4. 회고

.

5. 코드