11049

오답 여부: o

편집 시간: 2022년 3월 28일 오후 3:55

코드

i번째에서 j번째 행렬 연산의 최소값은

(i번째에서 j-1번째 행렬 연산의 최소값) + (j번째 행렬 연산) 과 (i+1번째에서 j번째 행렬 연산의 최소값) + (i번째 행렬의 연산) 이라고 착각해서 풀었다.

실제로는 양 끝에 추가하는 경우 뿐만 아니라 i번째에서 j번째 행렬 사이에 끊을 수 있는 모든 경우를 다 비교해봐야된다.

위 잘못된 풀이를 수정하여, i번째에서 j번째 행렬 연산의 최소값은

(i번째에서 k번째 행렬 연산의 최소값) + (k번째에서 j번째 행렬의 최소값) + (왼쪽 연산 결과와 오른쪽 연산 결과를 곱하는데 연산 횟수)

가 최소가 되는 k를 구하면된다.