백준 balanced cow subsets : 반으로 잘 쪼개 봅시다.

안녕하세요. 오늘은 USACO에 나왔던 Balanced Cow Subsets 문제를 풀어보도록 하겠습니다. 문제는 간단해요.

 

 문제를 해석하는 연습을 하셨다면, 이 정도는 밑줄을  치셨으리라 생각이 듭니다.

 

 왜 n이 20 이하일까요? 그냥 브루트 포스 해도 되는 거 아닐까요? 라는 생각을 하실 수도 있을 듯 싶어요. 그런데, 이 문제는 무려 옛날 USACO gold에 나온 문제입니다. 단순히 브루트 포스 해도 되었다면, Bronze에나 냈을 거에요. 그런데 Gold도 가끔 브루트 포스 하면 풀리는 게 있으니, 그렇게 해도 되지 않을까요?

 

 

---

 그러면 어떻게 브루트 포스를 할 건가요? n = 20이라면 많아봤자, 2^20개의 상태가 있으니까, 이들에 대해서 일일히 check를 해 보는 방법이 있습니다. 그렇게 오래 걸릴 거 같지 않아 보입니다.

 

 

 예를 들어 n = 4이고, 1번, 2번 3번 소를 선택한 Subset을 생각해 봅시다. 이 Subset이 Balanced인지 확인하려면 어떻게 해야 할까요? Subset의 subset을 만들어 보는 수밖에 없습니다. 예를 들어, 1과 3을 선택해 봅니다.

 

 

 vaild 한가요? 네. 여기서 1과 3을 선택했을 때 무게와 2를 선택했을 때 무게가 같은지 판단해 주면 됩니다. 아니면, 1만 선택해 보는 방법은 어떤가요?

 

 

 이것도 검사해 봐야 합니다. 즉, Subset의 원소의 수가 k개일 때, Subset의 부분 집합의 갯수는 2^k개가 됩니다. n = 20일 때 잘 생각해 봅시다. Subset의 원소의 수가 i개인 가짓수는 20Ci이고, 이 때 그것의 부분 집합의 갯수는 2^i개입니다. 이것을 수식으로 표현해 보겠습니다.

 

 수식을 풀어보다 보니, 이항 전개식이 나옵니다. 이걸 적절히 잘 묶어주면, 복잡도가 O(3^n)이 나온다는 것을 알 수 있어요. n이 20이면, 34억입니다. 시간 제한 1초. 2년 뒤에 다시 제출하면 가능할지도 모르겠습니다. 그렇지만, 5년 전에 30ms로 통과한 코드가 있다는 건, 이것 말고도 또 다른 풀이가 있다는 뜻입니다.

 

 

---

 그러면 각 subset에 대해서 knapsack처럼, 몇 번째 항까지 보았을 때, 합이 어떻게 나오는지를 찍어 볼 수도 있습니다. 그 후보해가 작으면 시도해 볼 만 합니다. 하지만, n의 값은 최대 20입니다.

 

 그러면 이런 식으로 데이터가 들어왔을 때 무용지물이 되어 버립니다. 이건 정확하게 2진수 표현과 맞아 떨어진다는 것을 알 수 있어요. 부분 집합을 어떻게 잘 뽑아보겠습니다.

 

 

  대충 0, 2, 3번 소를 뽑았다고 해 봅시다. 그러면, 이들의 subset의 합은 어떻게 나올까요? 1, 4, 8, 9, 5, 12, 13. 7개가 나옵니다. 이는 1 < 4이고, 1 + 4 < 8이기 때문입니다. 이런 저격 데이터가 한 둘이 아닌 것이 문제입니다. 20개 전체를 보았을 때에는 풀이가 생각보다 힘들다는 것을 알 수 있어요. 그러면 어떻게 하면 좋을까요? 10개 이하인 경우에는 그냥 돌려버리면 되고, n이 11 이상이라면 앞에 10개, 뒤에 n-10개씩 쪼개면 됩니다.

 

 그러면 반씩 쪼개서 무엇을 저장하면 좋을까요?

 

 0번, 2번, 3번으로 numbering 된 소를 골랐다고 해 봅시다. 그러면 {1, 4, 8}로 쓸 수 있을 겁니다.

 

 

 다시 작성된 {1, 4, 8} 중에서 1번째 것만 뽑았다고 구현하는 게 편합니다. 그러면, 선택된 소의 무게의 합은 4, 그렇지 않은 소의 무게의 합은 9, 그 차이의 절댓값은 5입니다. 이것을 front[state]에 모두 저장합니다.

 

 

 그 다음에 어떻게 할 거냐. 앞에 10번째까지 상태를 채우고 나서 뒤의 상태를 본다고 생각하면 편합니다. 예를 들어, 앞의 상태가 12이고, 뒤의 상태가 12라면, 2, 3번째를 뽑고, 10+2, 10+3번째를 뽑은 상태라는 것을 의미합니다. 그러면 이 상태들은, 둘로 나누었을 때 차이가 얼마나 나는지에 대한 정보도 저장하고 있을까요? 맞습니다.

 

 

 그런데, 차이가 d만큼 났다는 건 A팀과 B팀으로 나누었을 때, A의 무게 합을 a, B의 무게 합을 b라 하면, a-b가 d이거나, 반대로 b-a가 d일 수 있다는 이야기입니다. 이런 것까지 고려를 해야 하는 거 아닐까요? 라고 질문을 하실 수 있어요. 그런데 잘 생각해 봅시다.

 

 

 앞의 상태와 뒤의 상태의 차이의 절댓값 정보만 d, d였습니다. 그러면 이 경우에, 차이가 정말 d, d가 될 수도 있고, -d, -d가 될 수도 있고, d, -d가 될 수도 있을 거에요. 예를 들어 d, d였다고 해 봅시다. 앞의 A - 앞의 B 값이 d였고, 뒤의 A - 뒤의 B 값이 d였다면, 실질적으로 A가 선택한 소들의 무게 합에서 B가 선택한 소들의 무게 합을 빼면 2d가 됩니다. 그러면 답을 구할 수 없지 않느냐고 물어보실 수 있는데요.

 

 아닙니다. 그 경우, 둘 중 하나만 팀을 바꿔줘도 됩니다.

 

 

 따라서, 앞의 상태 st에 절댓값 차이가 k가 있다고 해 봅시다. 이 때 뒤의 상태 st'에 절댓값 차이가 k가 있다면, 앞의 10마리에서의 st와, 뒤의 10마리의 st'를 잘 조합한 상태는 Balanced Subset이라고 할 수 있습니다.

 

 

 예를 들어 앞에 12와 뒤에 12는 "12"라는 차이가 공통으로 들어있습니다. 따라서, 답 중 하나가 됩니다. 문제는, 앞의 3, 6, 12 등이 뒤의 12에 적어도 하나가 있는가를 빠르게 판단을 해야 하는데, 이것을 어떻게 하느냐가 문제입니다. 이것도 생각해 보면 복잡하지 않습니다.

 

 단순히 찾기만 한다면, unordered_map을 써도 됩니다. 그게 찜찜하다면, 정렬을 해 놓고, lower_bound 등으로 찾거나, set, map을 쓰셔도 됩니다. 다만, 제 방식으로 풀었을 때, 전처리랑 lower_bound를 썼을 때, 444ms가 걸렸다는 점을 참고로 하면 좋겠습니다.