백준 11049 - 행렬 곱셈 순서

https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

나름 대표적인 문제로, 학교 수업에서도 배웠다. 멍청하게도 풀이가 기억나지 않아 강의자료를 다시 보고 풀었다.

dp를 사용하는 문제로 풀이는 다음과 같다.

 

1) dp식 정의

이 문제는 dp식을 정의하기가 (내 기준) 까다로웠다. 반대로 dp식만 잘 정의할 수 있다면 초깃값과 점화식은 금방 설정할 수 있다.

 

문제에서 구하고자 하는 값이 무엇인가? '1번 행렬부터 N번 행렬까지 곱하는 데 필요한 최소 연산 횟수'이다. 그럼 이 값을 dp[1][N]으로 정의한다. 좀더 일반화하면 dp[i][j] = i번 행렬부터 j번 행렬까지 곱하는 데 필요한 최소 연산 횟수 라고 할 수 있다.

 

2) 초깃값

행렬 하나만 있을 때는 '행렬끼리의 곱셈'이 불가능하므로, dp[i][i] = 0이다.서로 인접한 두 행렬을 곱할 때는, 최소 횟수로 곱하는 방법이 둘을 직접 곱하는 방법 뿐이다. 행렬끼리의 곱에서의 연산 수는 앞 행렬 row * 앞 행렬 col (== 뒤 행렬 row, 항상 값이 같음) * 뒤 행렬 col이므로, dp[i][i+1] = matrix[i].row * matrix[i].col * matrix[i+1].col 이다.

 

3) 점화식

두 개가 아닌 여러 개의 행렬을 곱할 차례이다. 일단 식부터 설명하고, 이해를 돕기 위해 그림을 첨부한다.

자연수 len은 연산 횟수를 구하고자 하는 행렬 구간의 길이를 표현한다. 예를 들어 len = 3일 경우, dp[i][i+len]은 i부터 i+1, i+2, i+3번 행렬까지 총 길이 4의 행렬을 곱하는 최소 횟수를 의미한다.

 

그리고 i <= j < i+len인 자연수 j가 있다. j는 i부터 시작한 길이 len+1의 행렬을 두 구간으로 나눈다. 예를 들어 i=1, len = 3이라고 하자. 이때 j는 1부터 3까지의 값을 가질 수 있다.

 

j가 1일 경우, 구간은 1번 행렬 하나와, 2~4번 행렬로 나뉜다.

j가 2일 경우, 구간은 1~2번 행렬과, 3~4번 행렬로 나뉜다.

j가 3일 경우, 구간은 1~3번 행렬과, 4번 행렬 하나로 나뉜다.

 

이제 두 개의 새 구간을 이용해 원래 구간의 총 곱셈 횟수를 나타낼 수 있다. 원래 구간을 A, 새 구간을 각각 B, C, 각 구간 내의 곱셈 횟수를 Ma, Mb, Mc라 하자. 그리고 각 구간의 맨 앞 행렬의 row를 first, 맨 뒤 행렬의 col을 last라고 하자. 그럼 다음과 같은 식을 얻을 수 있다.

 

Ma = Mb + Mc + B.first * B.last * C.last

예를 들어 j = 2일 때 아래의 식을 통해 Ma = 118이 된다.

구간이 하나의 행렬을 가질 경우는 초깃값에서 언급했듯이 해당 구간 내의 곱셈 횟수가 0이 된다.

 

식을 코드로 옮겨보자.

 

dp[i][i+len]은 i <= j < i+len인 j에 대해, 구간을 j에서 둘로 나눴을 때 생기는 총 연산 횟수의 최솟값이다.

행렬 구간은 j를 기준으로 i ~ j, j+1 ~ i+len 둘로 나뉘며, 따라서 j에서의 연산 횟수는 dp[i][j] + dp[j+1][i+len] + matrix[i].row * matrix[j].col * matrix[i+len].col이 된다. 가능한 모든 j에 대해 연산 횟수를 구해, 최솟값을 dp[i][i + len]에 저장하면 된다.

 

반복문은 어떻게 구성하는가? 자연수 len에 대해 행렬 구간의 길이는 len + 1이라고 했다. 길이 2의 구간은 서로 인접한 행렬끼리의 곱으로 초깃값에서 구했으니 생략한다. len = N이면 행렬 구간의 길이가 N + 1이 되므로 범위를 초과한다. 따라서 len의 범위는 2 <= len < N이 된다.

 

각 len 값에 대해, '원래 구간'의 시작 위치 i가 가질 수 있는 값의 범위는 어떨까? 1번 행렬부터 시작할 수 있으니 i는 1부터 시작하며, 구간의 마지막 행렬 번호인 i + len이 N보다 작거나 같아야 하므로 1 <= i <= N - len이다.

 

그리고 구간을 나누는 위치 j는 위에서 설정했듯 i <= j < i + len으로 두면 된다.

 

실제 코드

for (int len = 2; len < N; len++) {

    for (int i = 1; i <= N - len; i++) {

        //i <= j < i + len에서의 최솟값 계산
        int min = INT_MAX;
        for (int j = i; j < i + len; j++) {

            //temp : 각 j값에서 연산 횟수
            int temp = dp[i][j] + dp[j + 1][i + len] + matrix[i].row * matrix[j].col * matrix[i + len].col;
            if (min > temp)
                min = temp;
        }

        dp[i][i + len] = min;
    }
}

//구하는 값 : 1부터 N까지 곱셈의 최소 연산 횟수
cout <<  dp[1][N] << endl;

dp식 정의가 어려울 때는 우리가 결국 어떤 값을 구해야 하는 지 되새겨보자. 우리는 문제에서 요구하는 답 (1번부터 N번까지 곱하는 최소 연산 횟수)을 찾아야 한다. 그러니 답의 내용 (1부터 N까지..)을 그대로 dp식(dp[1][N])에 옮겨오면 된다. 이런 정의가 만능 치트키는 아니지만, 다른 dp문제를 풀 때도 이 방법이 도움이 될 때가 종종 있을 것이다.