[알고스팟] Poly - 폴리오미노 (C++)

문제

https://algospot.com/judge/problem/read/POLY

algospot.com :: POLY

 

풀이

종만북 난이도: 중

 

폴리오미노 중에서도 세로로 단조인 것의 개수를 구해야 하는 문제. 

 

일단 폴리오미노는 한 변이라도 붙어이어야 하기 때문에 모든 정사각형은 이어저 있어야 한다.

또한 세로로 단조이기 위해서는 같은 세로줄이라면 모두 이어져야 한다.

 

따라서 위의 세로줄부터 num개의 사각형을 이어 붙이고 남은 사각형(remain_squ)으로 다음 세로줄을 몇 개의 사각형으로 이룰지 호출하는 재귀함수로 문제를 해결할 수 있을 것이다.

 

여기서 이전 정사각형의 개수(pre_squ)는 폴리오미노의 모양, 경우의 수에 영향을 미친다.

예를 들어 pre_squ =3 , 현재 정사각형 num = 2 라고 가정해보자.

 

두 세로줄이 결합하는 형태는 아래의 4가지 경우이다.

 

위의 그림에서 알 수 있듯이 위의 세로줄은 그대로 두고 아래 세로줄이 최소 한 칸이 이어지도록 왼쪽으로 이동시켜보면 가능한 형태의 개수는 (이전 정사각형의 개수) + (현재 정사각형의 개수) - 1인 것을 알 수 있다.

따라서 가능한 경우의 수는 pre_squ + num -1 이다.

 

남은 정사각형의 개수와 이전 정사각형의 개수를 매개변수로 넘겨 폴리오미노의 수를 반환하는 재귀함수를 아래라고 해보자.

int PloyCount(int remain_squ, int pre_squ)

 

현재 줄의 정사각형으로부터 아래의 부분이 어떤 형태의 폴리오미노를 취하고 있던, 이전 정사각형들은 현재 줄의 정사각형과만 이어지기 때문에 현재 줄의 정사각형의 개수를 num이라고 하면 가능한 폴리오미노 개수는 

(pre_squ +num -1) * PloyCount(remain_squ-num, num) 라고 나타낼 수 있다.

 

따라서 num이 (1 ~ remain_squ) 범위의 값일 때의 경우를 모두 더한 값이 

 PloyCount(remain_squ, pre_squ) = cache[remain_squ][pre_squ]의 값이 된다.

 

참고로 첫번째 줄의 사각형의 경우, 이전 사각형이 없기 때문에 예외 처리를 해주자.

 

 

본인의 경우, 세로줄의 순서 order와 remain_squ, pre_squ를 이용하여 문제를 해결하려 했다.

 cache는 cache[order][remain_squ], 해당 순서order일때 남은 사각형 remain_squ으로 구성 가능한 형태의 개수로 저장하려 했다. 

하지만 이런 경우 order와 remain_squ가 같더라도 pre_squ가 다르다면 전혀 다른 값이 나오지만 이미 계산한 값이라면 저장된 값을 그대로 사용하므로 틀릴 수밖에 없다.

 

또한 order와 상관없이 remain_squ과 pre_squ가 같다면 항상 같은 형태의 개수만이 존재하므로 order은 부분 문제를 구성하는데 전혀 상관없는 값이었다...

 

 

코드