전에 풀었던 행렬곱셈 문제와 동일한 로직이다. 문제의 핵심(dp누적의 핵심)은 이전 누적합이 새로운 누적합에 계속 중첩된다는 것. 때문에 i에서 j로 가는 모든 부분합에 대해 최솟값을 찾아 누적합값을 더해줘야 한다. 약간 예전에 처벌받은 벌에 대해 전과 괴심죄로 가중처벌 받는 느낌? 복리로 늘어나는 느낌? 그런 느낌의 수열. 대각선으로 덧셈을 진행(N*N인접행렬로 진행되며 중앙에서 멀수록 길이가 긴 행렬이며 합을 구할 때는 i에서 j까지의 중간 경유점k에 대해 분리해 2개의 합을 이루는 경우의 수를 모두 조사해준다. import sys input = sys.stdin.readline def solve(): N, A = int(input()), [0] + list(map(int, input().split(..