11049_행렬 곱셈 순서 (파이썬,설명)

문제는 더보기!

 

행렬 곱셈 순서 성공

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

18328

8414

5997

44.439%

문제

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

• AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
• BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.

같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

입력

첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

예제 입력 1 복사

3
5 3
3 2
2 6

예제 출력 1 복사

90

 

먼저 해당 문제는 이전글의 파일 합치기 유형과 상당이 유사했다!

 

파일합치기 문제를 풀었다면 풀 수 있을 문제일 것이다. 나 역시 자력으로 푸는데 성공했다!

 

파일합치기와 유사하게 dp를 2차원 배열로 두고 생각해보자.

 

 

 

이전에 누적합을 사용했지만 이번에는 필요가 없다는걸 깨달았다.

 

우선 문제에서 나오는 유형을 아래와 같은 한개의 리스트로 만들어주었다. 해당리스트의 이름을 n_lst라고 하자

 

[ 0, 5 , 3 , 2 , 6 ]

 

이러면 문제의 유형이 살짝 바뀌게 된다. 결국 우리가 곱할 수 있는건 저 좌표가 3개가 모였을 경우이다.

 

즉, 5,3,2    3,2,6 두개의 연산을 먼저 하는 경우로 나누어지게 된다.

 

이해가 잘 안된다면 우선 아래 내용을 먼저 읽어보자.

 

 

 

[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]

 

우리는 n+2 크기의 dp를 만들었다. n+2인 이유는 n_lst와 크기를 동일하게 해서 계산하기 편하기 위함이다.

 

그리고 행(가로)를 시작점, 열(세로)를 끝점이라고 생각해보자.

 

즉, dp[1][3]는 n_lst의 1번째~3번째인 5 3 2 까지의 행렬곱셈한 값이 들어간다고 생각하면 된다.

 

그렇다면 dp[1][4]에는 5 3 2 6 즉, 우리가 구하고자 하는 행렬곱셈의 값이 들어간다고 생각하자.

물론 dp[2][4]는 3 2 6의 행렬곱셈값이 들어가게 될 것이다.

 

만약 dp[1][2]와 같이 행렬이 하나인 경우는 연산결과가 0인 상태로 존재하게 될 것이다.

 

 

 

우리가 5 3 2 6 으로 주어진 값을 연산할때 5 3 2 를 먼저 연산하는 방법과 3 2 6를 먼저 계산하는 방법이 있을것이다.

 

5 3 2 를 먼저 계산한다면, 5 * 3 * 2  +   5 * 2 * 6 일 것이고

3 2 6 를 먼저 계산한다면, 3 * 2 * 6 +    5 * 3 * 6 일 것이다. 

 

 

결국 마지막에 더해지는 값은 n_lst의 처음값과 끝값이 5 * x * 6 꼴로 들어가게 될 것이다. x에는 그 사이값이 하나씩 들어가게 될 것이다.

 

즉, 처음값 * x * 끝값 꼴이 마지막에 더해지게 된다.

 

그럼 그 앞은 어떨까? 현재는 5 3 2 6 밖에 주어지지 않았기에 헷갈릴 수 있지만 만약 5 3 2 6 5 가 주어졌다고 가정해보자.

 

 

5 3 2 6 5 를 연산하는 방법은 아래와 같이 3가지이다.

 

5 3 2 6  을 계산하고 마지막 5랑연산          => 마지막 계산이 5 * 6 * 5

5 3 2  ,  2 6 5 을 계산하고 두 행렬을 마지막에 계산    => 마지막 계산이 5 * 2  * 5

3 2 6 5 을 계산하고 마지막 앞의 5랑 연산     => 마지막 계산이 5 * 3 * 5

 

 

그런데? 5 3 2 6을 계산한값, 3 2 6 5 를 계산한값은 결국 우리가 dp를 채워나가면서 이미 계산했던 값이기에 가져올 수 있다. 즉, dp는 아래와 같은 과정으로 채워지게 된다.

 

[0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 0, 0]
[0, 0, 0, 0, 36, 0]
[0, 0, 0, 0, 0, 60]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
--------------
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 90, 0]
[0, 0, 0, 0, 36, 90]
[0, 0, 0, 0, 0, 60]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
--------------
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 90, 140]
[0, 0, 0, 0, 36, 90]
[0, 0, 0, 0, 0, 60]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
--------------

 

 

자 간단하게 정리해보자. 우리는 시작점과 끝점을 가진 2차원 dp를 하나 만들었고 위에 설명한 과정에 의해 dp를 채워나가기만 하면 되는 것이다.

 

n = int(input())
lst = [[0,0]] + [ list(map(int,input().split())) for _ in range(n) ]
nlst = [ 0,lst[1][0] ] + [ lst[i][1] for i in range(1,n+1)]
dp = [ [0 for _ in range(n+2)] for i in range(n+2)]

for i in range(3,n+2):
    for j in range(1,n+3-i):
        # print('i',i,'j',j)
        tmp =[]
        for k in range(i-2):
            tmp.append( dp[j][j+k+1] + dp[j+k+1][j+i-1] + nlst[j] * nlst[i+j-1] * nlst[j+k+1] )
        dp[j][j+i-1] = min(tmp)

    # for p in dp:
    #     print(p)
    # print('--------------')

print(dp[1][n+1])

위 코드는 내가 짠 코드이다. 

 

이중 for문이 보이는데, i는 시작점 j는 끝점이 아닌, i는 구하고자하는 행렬 연산의 길이이다.

 5 3 2 6 이라 치면 i는 4이다. 그렇기에 3부터 시작하는 것이다.

 

j는 시작점이다!

 

위에서 말한 부분을 생각하면서 코드를 보면 이해할 수 있을 것이다! 헷갈린다면 주석을 해제해서 i,j의 값과 dp변하는 값을 보면 이해할 수 있을 것이다.