[프로그래머스] 12942 최적의 행렬 곱셈 - JAVA
·
알고리즘/문제풀이
[프로그래머스] 12942 최적의 행렬 곱셈 - JAVA문제https://school.programmers.co.kr/learn/courses/30/lessons/12942문제 분석조건여러 개의 행렬을 순서대로 곱할 때, 곱셈 순서(괄호를 치는 순서)에 따라 총 곱셈 연산 횟수가 달라진다. 주어진 행렬들의 곱셈에 필요한 최소 연산 횟수를 구하는 문제풀이방법DP를 이용하여 문제를 풀었다.`dp[i][j]`는 i번째 행렬부터 j번째 행렬까지 곱하는 데 필요한 최소 곱셈 연산 횟수를 의미한다. 행렬이 1개(`i == j`)일 경우 곱셈이 필요 없으므로 0으로 초기화 한다.`i`부터 `j`까지의 행렬 곱은, 중간의 한 지점 `k`를 기준으로 (`i ~ k`)까지의 곱과 (`k+1 ~ j`)까지의 곱, 이 두 결..