Codeforces Round #717 (Div. 2) C. Baby Ehab Partitions Again

https://codeforces.com/contest/1516/problem/C

문제요약:

수열에서 합이 정확히 전체 합의 절반인 부분 집합이 존재하지 않도록 만들자.

원소를 하나씩 집합에서 제외하는 연산을 할 수 있다.

 

 

풀이:

일단 정확히 합이 절반인 것이 존재하는지를 dp로 판단하자. O(100*2000*100)정도에 알 수 있다.

 

그렇다면 정확히 절반인 것이 존재한다고 하자. (없으면 0출력후 종료)

전체합이 홀수라면 그런 partition이 불가능함은 자명하다.

 

따라서 홀수인 원소가 하나라도 있다면 그 원소를 하나 제거하기만 하면된다.

그게 아니라면, 즉 홀수인 원소가 없다면, 이제 중요한 것은, 모든 원소는 짝수가 되고 즉 모든 원소를 동시에 2로 나눈다. 2로 나눈 새로운 수열에서 partition하는 것과 동치임이 자명하다.

 

동일하게 계속 수열의 모든 원소를 2로 나눠주면서 홀수인 것이 있는지 판정해주면 된다.

애드혹 적인 성질은, 항상 원소를 1개 없앰으로써 조건에 만족하게 만들 수 있다는 것이다.