문자열 자르기

• 사실상 파일 합치기와 동일한 문제이고, 그것은 곧 최적 이진 검색 트리와 동일한 문제임을 의미한다.
• 문제에서 주어지는 문자열의 위치들로부터 각각의 문자열의 길이를 구해서 C라는 배열에 저장해놓고 보면, 코스트 펑션이 같기 때문에, 조각난 상태에서 차례대로 합치는 것이나 합쳐진 상태에서 차례대로 잘라서 조각으로 만드는 것이나, 순서만 거꾸로일뿐 최적 방법은 똑같다는 것을 알 수 있다.
• 그래서 최적 이진 검색 트리에서 설명했듯, O(n^3)의 기본 DP 풀이, 거기에 크누스 최적화를 적용한 O(n^2) 풀이, Garsia-Wachs 알고리즘에 기반한 O(n^2) 또는 O(nlogn) 풀이가 모두 가능하다.
• 이 문제에서는 크누스 최적화를 이용한 O(n^2) 해법으로 통과가 가능하다. 아래 코드도 그것을 구현한 것.
  • 이렇게 구현할 경우, 구현에서 필요한 것은 각각의 문자열의 길이가 아니라, 그것에 대한 누적합이다. 그리고 인풋으로 들어오는 문자열의 위치들이 누적합과 동일하므로 그냥 사용할 수 있다. 결국 굳이 각각의 문자열의 길이를 계산할 필요는 없다.
• 실수하기 쉬운 부분은 인풋으로 받는 문자열의 위치들은 정렬이 되어있지 않다. 정렬하는 것을 잊지 말자.

"""Solution code for "BOJ 13260. 문자열 자르기".

- Problem link: https://www.acmicpc.net/problem/13260
- Solution link: http://www.teferi.net/ps/problems/boj/13260
"""


def main():
    N, M = [int(x) for x in input().split()]
    positions = [int(x) for x in input().split()]

    size = M + 1
    prefix_sum = [0, *sorted(positions), N]
    dp = [[0] * size for _ in range(size + 1)]
    opt = list(range(size))
    for l in range(1, size):
        for i in range(size - l):
            j = i + l
            dp[i][j], opt[i] = min((dp[i][k] + dp[k + 1][j], k)
                                   for k in range(opt[i], opt[i + 1] + 1))
            dp[i][j] += prefix_sum[j + 1] - prefix_sum[i]

    print(dp[0][size - 1])


if __name__ == '__main__':
    main()