블로그 이사 중입니다 >> gumgood.github.io

1500 최대 곱 본문

Problem Solving/문제 풀이

1500 최대 곱

gumgood 2018. 11. 9. 17:08

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
Tag
0 Comments
댓글쓰기 폼