[Baekjoon]백준 11049 행렬 곱셈 순서(골드 3) - C++, Python

문제설명

예제

문제를 살펴보면 행렬을 곱하기 위해 필요한 곱셈 연산을 최소화하였을 때의 경우의 수를 찾는 문제이다

행렬이 서로 곱해지기 위해선 a x b, b x c와 같이 행과 열의 개수가 같은 부분이 존재하여야한다

그래서 이를 구현하기 위해 어떻게 해야할까...하면서 문제를 다시 보니 행렬의 순서를 바꾸면 안 되고, 항상

순서대로 곱셈을 할 수 있는 크기만 주어지기 때문에 이를 고려하지 않고 정답을 찾아낼 수 있다

 

먼저 행렬을 저장할 2차원 배열을 하나 만들어주었다(matrix[502][2]) 뒤에서 설명하겠지만, 완성된 코드를 제출했더니

out of bound 오류가 발생하였다 계산 과정에서 오류가 있는 줄 알고 다시 검토해보고 일부 수정해보았음에도

오류가 지속적으로 발생하여 matrix의 크기를 더 크게하였더니 오류가 사라졌다

for(int len = 1; len < case_num; len++) { // 구간의 범위 -> 곱할 행렬의 개수
    for(int j = 1; len+j <= case_num; j++) { // 연산 시작 지점
        sol[j][len+j] = MAX;
        for(int k = j; k <= len+j; k++) { // 기준점
            sol[j][len+j] = min(sol[j][len+j], sol[j][k] + sol[k+1][len+j] + matrix[j][0] * matrix[k][1] * matrix[len+j][1]);
        }
    }
}

배열을 만들어서 적절한 위치에 값을 넣어준 뒤, 이전 문제처럼 for문을 두가지 사용하여 연산해주면 된다

sol[i][j] 배열에는 i부터 j까지의 최솟값이 저장되어있으며 이를 활용하여 점화식을 세워주면 된다

바깥쪽 for문에서는 최솟값을 구할 범위(곱할 행렬의 개수)를, 안쪽 for문에서는 연산의 시작 지점을 지정한다

그리고 sol배열에는 임의로 최대한 큰 값을 넣어주고 for문에서 최솟값을 갱신하면 된다

최솟값을 갱신하는 원리는 i부터 j까지의 최솟값을 구하기 위해선 i부터 i+2까지의 최솟값, i+2부터 i+4부터의 최솟값...

과 같은 형식으로 최솟값만을 저장하여 추후에 i부터 j까지의 최솟값을 구하게 되는 과정이다

즉, i부터 j까지의 최솟값이 i부터 i+3, i + 4부터 j까지의 합일때인지, i부터 i+4, i + 5부터 j까지의 합일때인지

확인하고 이를 갱신하는 작업이다 이를 C++로 작성하면 다음과 같다

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 1000000000

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int case_num;
    cin >> case_num;
    int matrix[502][2];
    int sol[502][502];

    for(int i = 1; i <= case_num; i++)
        cin >> matrix[i][0] >> matrix[i][1];

    for(int len = 1; len < case_num; len++) { // 구간의 범위 -> 곱할 행렬의 개수
        for(int j = 1; len+j <= case_num; j++) { // 연산 시작 지점
            sol[j][len+j] = MAX;
            for(int k = j; k <= len+j; k++) { // 기준점
                sol[j][len+j] = min(sol[j][len+j], sol[j][k] + sol[k+1][len+j] + matrix[j][0] * matrix[k][1] * matrix[len+j][1]);
            }
        }
    }
    
    cout << sol[1][case_num] << endl;

    return 0;
}

이를 Python으로도 작성하였는데, for문의 범위 지정(C++에서는 len + j와 같은 형식으로 for문 조건 실행)

에 있어서 헷갈리는 부분이 있었지만, 같은 로직을 통하여 정답임을 확인할 수 있었다(PyPy3 제출 권장)

import sys
input = sys.stdin.readline

case_num = int(input())
matrix = []
for _ in range(case_num):
    tmp = list(map(int, input().split()))
    matrix.append(tmp)
    
#print(matrix)
sol = [[0] * case_num for _ in range(case_num)]
for len in range(1, case_num): # 구간의 범위 
    for i in range(case_num-len): # 시작 지점
        j = i + len
        sol[i][j] = 2**31
        for k in range(i, j): # k를 기준으로 최솟값 갱신
            sol[i][j] = min(sol[i][j], sol[i][k] + sol[k+1][j] + matrix[i][0] * matrix[k][1] * matrix[j][1])
            
print(sol[0][-1])