wngywo12   2년 전

DP를 사용하지 않고 푸는 법 말고 DP를 사용해서 푸는 법 알려주시면 감사하겠습니다!(__)

k5nen   2년 전

굳이 DP를 쓰시겠다면, dp(x, y)를 x*y 크기의 초콜릿을 자르기 위한 최소 횟수라고 정의합시다.

첫 번째 커팅을 하고 나면 초콜릿은 x*i, x*(y-i) 크기의 두 조각, 또는 j*y, (x-j)*y 크기의 두 조각으로 나뉘겠네요.

이제 i = 1, 2, ..., x-1 / j = 1, 2, ..., y-1 범위에서 dp(x, i) + dp(x, y-i) 또는 dp(j, y) + dp(x-j, y)꼴의 값들 중 최솟값을 구하고 1을 더하면 됩니다.

DP를 안쓰고 푸셨으니 테이블을 그려보면 큰 의미는 없음을 확인하실 수 있을 겁니다.


wngywo12   2년 전

감사합니다!

ynifamily3   1년 전

https://www.acmicpc.net/board/view/48119


멍청하게(?) 푼 결과가 있습니다.

댓글을 작성하려면 로그인해야 합니다.