BOJ 28059

https://www.acmicpc.net/problem/28059
 
 
코드
http://boj.kr/e459a94c63ce440d97b82cb50426bec6
 
2023 KAIST RUN Spring Contest G
 
난이도 : D4
 
Elapse Time : 60min
 
문제를 보고 한 첫 번째 추측은 $s$에서 최댓값을 남겨놓고 마지막에 사용하는 것이 이득일 것 같다는 것이었다. 최댓값을 제외한 $n-1$개의 수로 최대한 작은 숫자를 만들어놓고 최댓값과 마지막에 묶어주는 전략을 세웠다. 예제를 분석하면서 한 두 번째 추측은 $n-1$개의 수 중 몇 개를 골라 두 그룹으로 나누는 모든 경우 각 그룹의 숫자 합의 차 중 최솟값을 만들 수 있을 것 같다는 것이었다. 두 번째 추측이 맞다면 최댓값 대신 다른 수를 남겨놓는 경우 최솟값이 더 작아지더라도 최댓값을 남기는 것이 더 이득이 된다. 최솟값의 감소량이 최댓값의 감소량보다 작거나 같기 때문이다. 그러므로 두 번째 추측이 맞는지 판단을 해야 했는데 이는 두 그룹에서 하나의 그룹을 더하는 그룹으로 설정하고 다른 하나의 그룹을 빼는 그룹으로 설정했을 때 이를 그대로 실행할 수 있으면 된다는 생각이 들었다. 그룹을 나누는 과정은 bitset을 활용한 dp를 사용했다. 여기서 문제는 $n$개의 원소에 대해 bitset dp를 하려면 시간과 공간복잡도가 모두 $O(n^2s)$가 된다는 것이었다. 각 원소의 최댓값이 $10^5$이기 때문에 숫자가 20개만 있으면 합이 같은 두 그룹을 충분히 설정할 수 있을 것이라는 생각이 들어 bitset dp를 하다가 합이 0이 되는 두 그룹으로 나눌 수 있으면 dp를 종료하는 방식을 사용했다. bitset dp의 결과를 이용해서 차이가 최소가 되는 두 그룹의 원소들을 2개의 벡터에 저장해 놓고 각각의 벡터에서 하나씩 원소를 뽑아 두 수의 차이를 큰 원소를 뽑은 벡터에 집어넣는 방식을 사용하면 하나의 그룹은 더하고 하나의 그룹은 빼는 연산을 할 수 있다는 것을 알게 되었다. 차가 최소인 두 그룹이기 때문에 둘 중 하나의 벡터가 비었을 때 다른 벡터에 원소가 2개 이상인 경우는 없다 것을 깨달았고 이 방식을 통해 해를 구성했다. 0-base를 사용하다가 1-base로 코드를 고치는 과정에서 실수가 있었고 $n=2$일 때 예외처리를 해주지 않아 2번의 WA를 받았다.