백준 11049 행렬의 곱셈 순서 [c++]

07 Jul 2022 in Develop / Solving

c++

문제 분석

• n개의 행렬이 주어진다.
• m * n, n * k의 행렬을 곱하면, m * n * k번의 연산을 하게 된다.
• n개의 행렬을 곱하는 데에, 가장 적게 연산하고 싶은데, 이 때의 연산수는 얼마인가.

입력조건

행렬의 갯수 n
n줄에 걸쳐서 {
	각 행렬의 r c
}

풀이과정

• 문제를 보고 굉장히 막막하여서, 알고리즘 보기를 눌러보았고, 다이나믹 프로그래밍이 적혀 있는 걸 보고 큰 힌트를 얻었다.
• n * n 크기의 보드를 만들어서, 각 행렬을 곱해갈 때의 최소 연산 수를 구한다.
• 이게 모든 경우의 수를 고려할 수 있냐고 생각할 수 있지만, 놀랍게도 고려할 수 있다.

• 보드는 i * i 대각선을 기준으로, 위쪽의 반만 사용한다.

• 우선, i,i 위치에 행렬값들을 입력받는다.
• dp순회를 해야 하는데, c번째 행의 c-1 ~ 0순서로 역으로 dp를 진행한다.
• (r, c)위치를 채울 수 있는 경우의 수는 (r, r) * (r+1, c) ~ (r, c) * (r+c-1, c) 의 c-r개이다.
• 이들을 고려하며 dp를 채워가면, (0, n-1)위치에 원하는 값을 얻게 된다.

전체 코드

#include <iostream>
#include <limits>

#define INF numeric_limits<int>::max()

using namespace std;

struct matrix {
    int r;
    int c;
    int sum = 0;
};

int main() {
    int n;
    cin >> n;

    matrix map[n][n];
    for(int i = 0; i < n; i++)
        cin >> map[i][i].r >> map[i][i].c;
    // 입력 완료.

    for(int c = 0; c < n; c++) {
        for(int r = c-1; r >= 0; r--) {
            //map[r][c] 위치를 만들어야 함.
            
            for(int d = r; d < c; d++) {
                // map[r][d] 에서 r 가져옴;
                // map[r+d][c] 에서 c 가져옴;
                int tmpsum = map[r][d].sum + map[d+1][c].sum + (map[r][d].r * map[r][d].c * map[d+1][c].c);

                if(map[r][c].sum == 0) {
                    map[r][c].sum = tmpsum;
                    map[r][c].r = map[r][r].r;
                    map[r][c].c = map[c][c].c;
                }
                else if(tmpsum < map[r][c].sum) {
                    map[r][c].sum = tmpsum;
                    map[r][c].r = map[r][d].r;
                    map[r][c].c = map[d+1][c].c;
                }
            }
        }
    }
    cout << map[0][n-1].sum;
}