[C++] 알고스팟/동적계획법 - 폴리오미노

문제 링크

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

algospot.com :: POLY

 

세로로 단조인 폴리오미노는 각 행의 사각형들이 모두 연속해서 붙어있어야 합니다.

같은 행에서 사각형들 사이에 공간이 있으면 안된다는 것을 의미합니다.

 

이 형태의 폴리오미노를 구하기 위해서는

첫 번째 행부터 내려가면서 각 행에서 사각형을 놓을 수 있는 모든 방법을 세어주면 됩니다.

n이 3일 때 첫 번째 행에 올 수있는 사각형은 1, 2, 3개로 총 3가지 경우가 올 수 있습니다.

 

첫 번째 행의 사각형 개수를 정하면 두 번째 행으로 내려가서 1개부터 남은 사각형 만큼을 놓고 다시 아래 행을 내려가는 방식으로 마지막 행까지 모두 구해야 합니다.

 

 

사각형을 놓는 방법은 윗 행의 사각형 개수에 영향을 받습니다.

첫 번째행의 사각형 개수가 a개가 놓여있고 두 번째 행에 사각형을 b개 놓을 때 a + b - 1 가지 방법만큼 올 수 있습니다.

 

따라서 다음 행으로 내려갔을 때의 모든 방법의 수에 현재 행에서 사각형을 놓는 방법의 수 만큼을 곱해줘야 합니다.

그리고 이를 사각형 1개를 놓았을 때 부터 남는 사각형만큼을 놓았을 때의 모든 방법을 더해주면 답을 구할 수 있습니다.

 

 

구현 코드