컨벡스 헐 트릭 (1) 썸네일형 리스트형 [BOJ] 10067 수열 나누기 문제 링크: https://www.acmicpc.net/problem/10067 문제 요약음이 아닌 정수 $n$개로 이루어진 수열이 있다. 이 수열을 $k+1$개로 나누어야 하는데, 한 번 나눌 때 마다 새로 나누어진 각 부분의 원소의 합을 곱한 것 만큼의 점수를 얻을 수 있다. 이 때 얻을 수 있는 점수의 최댓값과 그 순서를 구하는 문제이다.$2 \leq n \leq 100,000$, $1 \leq k \leq \min(n-1,200)$ 이다. 풀이 과정 가장 먼저 해야 할 관찰은 어느 순서로 수열을 자르던 간에 최종적으로 얻는 점수에는 변함이 없다는 것이다. 만약 어떤 부분을 2번 잘라 3개의 수열로 나누고, 이 수열의 합을 각각 $S_1$, $S_2$, $S_3$ 이라고 하자. 만약 왼쪽을 먼저 자.. 이전 1 다음