풀이 방법 dp 문제인데 문제를 부분 문제로 나누기 어려운 문제 였다. 처음에는 정사각형 하나를 두고 상하좌우로 사각형을 붙이는 형태로 부분 문제를 쪼개려고 생각 했지만 이러면 중복되는 부분을 다 제거 하기가 복잡해서 실패 했다. 정답은 층별로 부분 문제를 쪼개는 것이다 재귀 함수로 현재 남은 상자수와 각 재귀마다 첫 층에 쓸 상자수를 보내주고 함수 안에서 for 문을 돌며 2번째 층에는 몇개의 상자를 사용할지 선택후 함수 리턴값을 더하면 된다 여기서 리턴값에 first + second - 1를 곱해주어야 한다 1층과 2층을 한 칸씩 옆으로 이동시키면 다른 경우가 되기 때문이다. 시간 복잡도는 O(n^3)이다. #include #include #include #include const int MOD = ..