BOJ 16531

https://www.acmicpc.net/problem/16531

 

코드

http://boj.kr/0b3b16452bad451897d1fd5844b4292b

 

ICPC Latin America Regional Contests 2018 K

 

난이도 : P2

 

Elapse Time : 20min

 

문제를 보고 예전에 풀었던 #8230과 비슷하다는 생각을 했다. #8230에서도 정렬을 하고 가장 작은 것과 다른 수의 비교로 문제를 풀었기에 여기서도 정렬을 해놓고 비슷하게 하면 되지 않을까 싶었다. #8230과의 결정적 차이는 여기서는 $2^N$개의 조합을 모두 본다는 것이었다. 이를 바탕으로 한 첫 번째 관찰은 가장 작은 값은 모든 음수를 다 더한 값이 되고 두 번째로 작은 값은 0이 존재한다면 두 값은 같을 것이고 아니면 절댓값이 가장 작은 음수가 빠졌거나 값이 가장 작은 양수가 더해졌거나 둘 중 하나라는 것이었다. 두 번째 관찰은 특정 수 $x$가 존재한다면 수열은 $a_i$와 $a_i+x$를 원소로 가지는 두 수열로 쪼갤 수 있다는 것이었다. 이를 바탕으로 재귀 함수를 짜서 답을 구할 생각을 했다. 정렬된 수열과 현재까지의 원소를 함수의 인자로 넘기면 $v[1]-v[0]$의 값을 절댓값으로 갖는 두 수중 하나가 존재한다. 두 경우에 대해 새롭게 추가될 수를 $x$라고 하자. $x$의 값을 기반으로 $x$를 제외했을 때 만들어질 수열을 구하여 이 수열과 현재까지의 원소에 $x$를 추가하여 인자로 넘겨 재귀를 해주면 된다.

 

태그에 비트마스킹이 있어 다른 풀이가 존재함을 알게 되었다. 비슷한 논리를 사용하지만 약간의 차이가 존재한다. 79brue님의 코드를 참고하여 풀이를 알아보았다. 재귀에서 배열을 두 개로 나눌 때 배열 값에서는 차이가 있지만 differance array에서는 차이가 나지 않는다. 이것은 답의 모든 배열은 절댓값을 씌우면 동일해진다는 것을 의미한다. 그러므로 양수 배열을 구해놓고 각각에 $1$ 또는 $-1$을 곱하는 $2^N$가지의 경우에 대해 답이 될 수 있는 것만 출력해 주면 된다.