최적의 행렬 곱셈

ptm0304·2019년 11월 26일
0

알고리즘

목록 보기
4/13

문제출처: https://programmers.co.kr/learn/courses/30/lessons/12942

문제설명

크기가 a by b인 행렬과 크기가 b by c 인 행렬이 있을 때, 두 행렬을 곱하기 위해서는 총 a x b x c 번 곱셈해야합니다.
예를 들어서 크기가 5 by 3인 행렬과 크기가 3 by 2인 행렬을 곱할때는 총 5 x 3 x 2 = 30번의 곱하기 연산을 해야 합니다.

행렬이 2개일 때는 연산 횟수가 일정 하지만, 행렬의 개수가 3개 이상일 때는 연산의 순서에 따라서 곱하기 연산의 횟수가 바뀔 수 있습니다. 예를 들어서 크기가 5 by 3인 행렬 A, 크기가 3 by 10인 행렬 B, 크기가 10 by 6인 행렬 C가 있을 때, 순서대로 A와 B를 먼저 곱하고, 그 결과에 C를 곱하면 A와 B행렬을 곱할 때 150번을, AB 에 C를 곱할 때 300번을 연산을 해서 총 450번의 곱하기 연산을 합니다. 하지만, B와 C를 먼저 곱한 다음 A 와 BC를 곱하면 180 + 90 = 270번 만에 연산이 끝납니다.

각 행렬의 크기 matrix_sizes 가 매개변수로 주어 질 때, 모든 행렬을 곱하기 위한 최소 곱셈 연산의 수를 return하는 solution 함수를 완성해 주세요.

helper 메소드는 매트릭스의 x ~ y 범위 안에서 최소값을 반환한다. 계산한 최소값은 dp[x][y]에 저장해주고 이미 계산된 최소값이 있는지 확인함으로써 쓸데없는 계산낭비를 방지한다.

이 부분이 이 문제의 핵심 코드이다. (x ... y) 범위 안에 있는 행렬들을 곱했을때 최소값을 구해야하기 때문에 (x ... i) 범위안에 있는 행렬의 곱셈 최소값과 (i + 1 ... y) 범위 안에 있는 행렬의 곱셈 최소값을 더해준뒤 남은 두 행렬을 곱해서 더해준다. 이때 남은 행렬은 [mat[x][0], mat[i][1]], [mat[i][1], mat[y][1]] 이 되기 때문에, mat[x][0] mat[i][1] mat[y][1] 를 더해주면 된다.

0개의 댓글