문제
https://school.programmers.co.kr/learn/courses/30/lessons/12942
입력
각 행렬의 크기 matrix_sizes
출력
각 행렬의 크기 matrix_sizes 가 매개변수로 주어 질 때, 모든 행렬을 곱하기 위한 최소 곱셈 연산의 수를 return
풀이
제한조건
- 행렬의 개수는 3이상 200이하의 자연수입니다.
- 각 행렬의 행과 열의 크기는 200이하의 자연수 입니다.
- 계산을 할 수 없는 행렬은 입력으로 주어지지 않습니다.
접근방법
DP를 해결하여 풀 수 있는 문제이다.
처음에는 단순하게 생각을 했었다.
앞에서부터 3개씩 행렬을 보며, 최소 횟수로 곱해 나가면 최소가 될 것이라 생각했다.
그렇게 단순 구현을 했으나, 틀렸고 그 이유는 A(B(CD))의 순서처럼 곱해서 최소가 된다면, 순서대로 진행했을 때 정답이 될 수 없기 때문이다.
따라서 다른 접근 방법으로 접근하였다.
언젠가 같은 접근방법으로 풀었던 문제가 있는데 문제 이름이 기억이 나지 않는다.
재귀를 이용해 풀어보자.
곱셈을 해야 하는 행렬이 ABCDE 총 5개라고 생각해 보자.
5개의 행렬에서 발생할 수 있는 경우를 따져봐야 하는데.
분할 정복처럼 조금 더 작은 문제로 나누어보자.
ABCDE를 각각 두 덩어리로 나눈다.
그럼 A / BCED 또는 AB / CDE와 같은 형식으로 나누어지는데 이때 나누어진 부분에 대해서 다시 두 덩어리로 나눌 수 있다면 나눈다.
그럼 결국 2개의 행렬을 곱해서 1개의 행렬로 바꿀 때, 몇 번의 연산이 필요하고 어떤 행렬로 변하는지 알 수 있게 된다.
- 요약
1. 입력의 전체 길이를 구해본다.
2. 입력을 2개의 작은 문제로 나눈다.
( 0번 행렬~k번 행렬 + k번 행렬~N번 행렬 )
3. 작은 문제의 답을 계산한다.
4. 작은 문제의 답 중, 최소값을 큰 문제의 답으로 정한다.
5. 2~4 반복코드
class Solution {
static int[][] dp, arr;
public int solution(int[][] matrix_sizes) {
int answer = 0;
int len = matrix_sizes.length;
dp = new int[len+1][len+1];
arr = matrix_sizes;
answer = search(0, len);
return answer;
}
public int getMultiplyCount(int start, int end){
// 해당 구간을 구한적이 없다면 계산해본다.
if(dp[start][end] == 0)
dp[start][end] = search(start, end);
return dp[start][end];
}
public int search(int start, int end){
if(start + 1 == end)
return 0;
int result = Integer.MAX_VALUE;
// 중간범위가 end를 포함하게 설정하고, 구하고자 하는 범위가 k~k구간일 경우 0을 리턴하게 한다.
for(int mid = start + 1; mid < end; ++mid){
// 왼쪽 부분의 결과
int leftCount = getMultiplyCount(start, mid);
// 오른쪽 부분의 결과
int rightCount = getMultiplyCount(mid, end);
// 합치며 생기는 부분의 결과
int current = arr[start][0] * arr[mid][0] * arr[end-1][1];\
// 그 중 최소값이 정답
result = Math.min(result, leftCount + rightCount + current);
}
return result;
}
}