백준 14606. 피자 (Small)

tose33 2022. 12. 27. 14:30

14606번: 피자 (Small)

예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작

www.acmicpc.net

a + b = n 일때 a * b 가 최대인 경우는 a와 b를 최대한 균등하게 나눈 경우다.

예를들어 n=9라면 a=5,b=4 일때 a*b가 최대가 된다.

따라서 점화식은

d[i] = (a * b) + d[a] + d[b]