Prob No.066E : 균형잡힌 부분집합 [CH03.4.USACO(Gold)]
balanced cow subsethttp://koistudy.net/?mid=prob_page&NO=1646
https://www.acmicpc.net/problem/5879
구재현 선배님의 도움으로 푼 문제다.
문제에서 미리 전처리를 해주는 것이 매우 중요하다.
이 방법은 각 원소를 앞의 반은 흰색, 나머지는 갈색으로 칠한다.
만약 집합 S가 균형이 잡혀있으려면…
S의 두 부분집합 A, B의 합이 같아야 한다.
그러면 (A에 있는 갈색 원소의 합) - (B에 있는 갈색원소의 합) = (B에 있는 흰색원소의 합) - (A에 있는 흰색원소의 합)
이 성질을 이용하면 문제를 풀 수 있다.
3^(n/2)의 DFS를 앞의 반과 뒤의 반에 대해서 따로 따로해주며 값을 배열에 저장한다.
DFS시 각 레벨에서 선택은 3가지다. a[i]를 빼거나 더하거나 아무것도 하지 않거나.
이후 inch worm algorithm 처럼 정렬된 두 배열에서 두 포인터의 크기를 비교해주면서 진행한다.
문제는 두 포인터가 가르키는 배열이 같을 경우인데 이건 걍 같은걸 for문 돌리면서 다 봐주면 된다.
나도 이게 왜 시간 안에 통과되는지 이해가 잘되지 않는다.
나도 구사과처럼 정보 잘하고 싶다 ㅠㅠ
소스코드 bal
