USACO 2013 March Bronze - Breed Assignment

가장 쉬운 방법은 재귀적으로 모든 경우를 다 살펴보는 것이다. 재귀함수에서는 소의 번호 x만 있으면 된다. 1번 소부터 시작해서 조건을 만족하는지 차례로 살펴보면, 최악의 경우 O(K*3^N)의 시간 안에 답을 구할 수 있다. 하지만 적절히 커팅을 하면 대략 O(3^N)의 시간 안에 답을 구할 수 있을 것이다.

재귀함수를 쓰지 않고 답을 구할 수도 있는데, 3진법의 N자릿수를 생각해본다. 그리고 0부터 3^N-1까지 모든 경우를 반복문으로 확인해도 O(3^N)의 시간 안에 답을 구할 수 있다.