gshscs

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

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

FJ에게는 세 가지 다른 품종(Holstein, Jersey, Guernsey)의 소 N마리(2 <= N <= 15)가 있다.

불행하게도, FJ는 소들의 품종을 잊어버렸다! 다행히도 FJ는 소들 사이의 관계를 K(1 <= K <= 50)개 알고 있다. 예를 들어, 1번과 2번 소가 같은 품종이거나, 1번과 5번 소가 다른 품종인 것을 알고 있을 수도 있다.

이러한 관계가 입력으로 주어질 때, 소들의 가능한 품종의 가짓수를 구하는 프로그램을 만드시오.(입력된 정보가 모순일 때는 0을 출력한다.)

PROBLEM NAME : assign

INPUT FORMAT

Line 1 : 두 정수 N과 K가 주어진다.

Line 2~K+1 : x번 소와 y번 소의 관계를 나타내는 정보가 주어진다.(1 <= x, y <= N, x != y) 입력은 “S x y”나 “D x y”로 주어지는데, “S x y”는 x번 소와 y번 소가 같은 품종임을 나타내고, “D x y”는 x번 소와 y번 소가 다른 품종임을 나타낸다.

OUTPUT FORMAT

Line 1 : 소들의 가능한 품종의 가짓수를 출력한다.

SAMPLE INPUT

4 2 S 1 2 D 1 3

SAMPLE OUTPUT

18

http://www.usaco.org/index.php?page=viewproblem2&cpid=261

소들의 거리가 K 이하일 때 혼잡하다는 데 주의할 필요가 있다. 거리가 K 이하인 모든 경우를 찾으면 될 것이고, 그러면 O(NK)의 시간이 소요될 것이다. 하지만 Sliding Window를 쓰면 계산량을 크게 줄일 수 있다.

[7 3 4 2] 3 4 
7 [3 4 2 3] 4 -> 최대 혼잡도 3
7 3 [4 2 3 4] -> 최대 혼잡도 4

한 Window 안에서 품종이 같은지 확인하기 위해서 해싱을 쓰면 된다.