1500 최대 곱

C++11

dp[i][j] := 합이 i인 j개의 양의 정수들을 곱했을 때 최대 값

case 1) j==1 이면, i 숫자 하나만 골라야 하므로 dp[i][1] = i;

case2) i > j 이면, {j-1개의 수} + {새로운 수}로 생각할 수 있다.

 j-1로 만들 수 있는 수에 추가할 수 있는 수들을 다 넣어보면 가장 큰 값을 얻을 수 있다.

이를 점화식으로 정리하면

if j==1, dp[i][j] = 1;

elss, dp[i][j] = max(k*dp[i-k][j-1]) where k = {1,2,3,...,i-1}.

모든 i, j에 대해 가능한 모든 k를 체크를 확인하는데,

i, j는 각각 S, K가지가 있고 k도 최대 S-1이므로

O((S^2)K)

저작자표시비영리변경금지

'Problem Solving > 문제 풀이' 카테고리의 다른 글

1018 체스판 다시 칠하기  (0)	2018.11.13
11365 !밀비 급일  (0)	2018.11.13
1500 최대 곱  (0)	2018.11.09
11091 알파벳 전부 쓰기  (0)	2018.11.09
16212 정열적인 정렬  (0)	2018.11.09
9971 The Hardest Problem Ever  (0)	2018.11.08