https://www.acmicpc.net/problem/5463
문제요약
- n * m(50, 50) 격자
- 수평/수직으로 두 조각으로 자를때마다 전체 판 비용 발생
- 최소의 금액 구하기
- 시간 제한 3초
접근법
- [시작][시작][끝][끝] 을 쪼갰을때 최소비용 dp로 생각하면
- 50 50 50 50 (가로 + 세로) = 625,000,000 = 약 6억
- 하지만 시작 <= 끝 을 만족해야할테고, 가로+세로도 항상 100은 아닐테니 대략 나누기 이를 하면 약 3억(나누기 2를 한 이유는 1 + 2 + ... 를 하면 n^2 / 2 정도여서 대략 추측함)
- 전체 판 비용 계산을 위해 부분합 이용
newbieski