(python) 백준 11049 :: 행렬 곱셈 순서(DP)

by

(행렬 곱셈 순서)

# 문제
크기가 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. 두 행렬의 곱셈 연산 수 계산

행렬 1과 행렬 2를 곱해봅시다!

크기 5 X 3인 행렬 1크기 3 X 2인 행렬 2곱할 때
연산 횟수는 3을 2번 더하는 것을 5회 반복한다.

수식으로 표현하면,
행렬 1의 행 X 행렬 1의 열 X 행렬 2의 열 된다

이번에는 행렬이 4개일 때 연산의 수를 구해봅시다!

2. 3개 이상의 행렬의 곱셈 연산 수 계산

(행렬 1 X 행렬 2) X (행렬 3 X 행렬 4) 순서대로 곱셈할 때의 연산 수를 구해보자!

  • 위의 두 행렬의 곱셈 연산 횟수와 동일하게 사용합니다.
    1, 2) 묶인 행렬 사이의 곱셈 연산의 수와 결과첫 번째,
    3) 모두 결과를 곱할 때작업 수까지 그냥 추가

3. 계산 건수 확인

범위가 행렬 1에서 행렬 3인 경우

행렬의 범위가 1에서 3인 경우 다음과 같은 두 가지 경우가 있습니다.
이 두 가지 경우를 계산할 때 더 작은 값이 최소 작업 수가 됩니다.

범위가 행렬 1에서 행렬 4인 경우

행렬의 범위가 1에서 4인 경우 세 가지 경우가 있습니다.

마찬가지로 각각의 경우에 연산 횟수를 계산하면 그 중 가장 작은 값이 최소 연산 횟수가 됩니다.

먼저 작은 범위를 계산해야 합니다.

이와 같이 4개의 행렬의 경우, 행렬은 3을 곱할 때 최소 연산 수를 알아야 합니다.
연산의 수는 4개일 때 얻을 수 있음을 알 수 있다.
(마찬가지로 3개의 행렬과 마찬가지로 2개의 행렬을 곱하여 계산할 때 최소 연산 수를 알아야 합니다.)

그러므로
먼저, 획득하고자 하는 현재 영역 내에서 발생할 수 있는 더 작은 영역에 해당하는 동작을 수행한다. 해야한다.
(받은 최소 오퍼레이션 수를 dp 테이블에 저장하고 필요할 때 불러온다.)

이제 이 정보를 사용하여 코드로 구현해 보겠습니다.

화신

1. dp 테이블 준비!

  • 최소한의 연산으로 값을 저장 dp 테이블활용
dp = ((0)*(N) for _ in range(N))

👉 저장할 값
dp(시작행렬)(끝행렬) = 최소 연산 횟수

👉 예시
문제에서 주어진 예시 (A의 크기가 5×3, B의 크기가 3×2, C의 크기가 2×6)
(AB)C의 연산 횟수는 5×3×2 + 5×2×6 = 30 + 60 = 90번
A(BC)의 연산 횟수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이므로
dp(A)(C) = 90이 된다.

2. 간격이 가장 작은 면적부터 계산합니다.

위에서 수술 건수를 살펴보았듯이,
연산 수에 행렬 4를 곱한 수를 알려면 연산 수에 3을 곱한 수를 알아야 합니다.
3을 곱한 작업 수를 찾으려면 2를 곱한 작업 수를 알아야 합니다.

그러므로, 간격이 작은 범위에서 시작하여 작업 수를 계산합니다.할 것입니다 (가장 작은 간격에서 계산하십시오.)

# 1. 간격이 1인 범위 먼저 전부 계산
행렬 1 ~ 2, 행렬 2 ~ 3, 행렬 3 ~ 4

# 2. 다음으로 간격이 2인 범위 전부 계산
행렬 1 ~ 3, 행렬 2 ~ 4

# 3. 마지막으로 간격이 3인 범위 계산
행렬 1 ~ 4

  • 가장 작은 간격에서 하나씩 계산하려면 term 변수를 만들어 ‘1’에서 ‘행렬 수 -1’까지 증가하는 간격으로 사용합니다.

  • 사용,
    처음에는 term가 1이므로 두 행렬을 곱해야 합니다. 행렬 satrt그리고 행렬 start+1된다
    (start1이다 행렬 1수업 행렬 2의 작업 수를 계산합니다.)

for term in range(1, N):
    for start in range(N):  # 현재 범위의 첫행렬: start, 끝행렬: start + term
        if start + term == N:  # 범위를 벗어나면 무시
            break

3. 계산할 영역 내에서 바인딩되는 경우를 고려하십시오.

1학기 행렬 start그리고 행렬 start+1곱한 작업 수를 직접 찾을 수 있습니다.
항이 1보다 큰 경우 괄호 안에 넣어 연산 순서를 변경할 수 있으므로 다른 경우가 발생합니다.

예를 들어 항이 3이면 행렬 4개의 곱을 계산해야 합니다.
(시작 행렬: start끝 행렬: start+3 start, start+1, start+2, start+3)

괄호 안에 있는 경우 각 괄호 안의 행렬 수1에서 3까지 가능합니다.
즉, 행렬은 괄호 안에 있습니다. 최소 1개~에 최대 term개된다

괄호 세트의 모든 인스턴스를 계산하려면
start에서 start+term 이전보다 증가 t 변수 사용

그만큼 t 변수를 사용
괄호로 묶인 그룹을 기준으로 왼쪽 그룹과 오른쪽 그룹을 나눕니다.

왼쪽 묶음의 행렬 수는 다음과 같습니다. 최소 1개에서 최대 term개1씩 증가

1) 왼쪽 그룹의 작업 수

dp(start)



  • 왼쪽 번들의 출력 행렬은 다음과 같습니다. start로 고정
    (왼쪽 묶음의 시작 행렬은 항상 동일함)
    

    • 

  • 묶음의 왼쪽 끝 t된다
    (t~이다 start왼쪽 묶음의 끝에서 1씩 증가함에 따라 start, start+1, start+2, start+3..., 계산 중인 범위의 마지막 행렬 - 1된다.)
    

    • 



2) 오른쪽 그룹의 작업 수




dp(t+1)(start+term)


    

  • 왼쪽 매트릭스 번들의 끝은 t오른쪽 번들의 시작도 마찬가지입니다. t+1된다
    • 

  • 오른쪽 묶음의 끝은 마지막 묶음에 해당합니다. start+term된다
    (처음부터 Term!!! 간격으로 행렬까지 계산하기 때문에)
    • 



3) '왼쪽 그룹화 결과 행렬 X 오른쪽 그룹화 결과 행렬'의 연산 횟수


    

  • 

    두 행렬에 두 세트의 결과를 곱한 횟수를 찾는 것과 동일한 작업을 수행할 수 있습니다.
    

    • 

  • 

    왼쪽 묶음의 결과
    행L: 왼쪽 그룹의 첫 번째 행렬의 행 == arr(start)(0)
    열L: 왼쪽 묶인 행렬의 열 == arr

    • 

  • 

    올바른 번들의 결과
    행R: 오른쪽 그룹의 첫 번째 행렬의 행 == arr

    • 

  • 

    행L    엑스 열L 엑스 열R
    

    arr(start)(0) * arr

    • 





1~3의 합이 최소가 되는 값 dp(start)(start+term)에 저장




        dp(start)(start+term) = int(1e9)  # 지금 계산할 첫행렬과 끝행렬

        for t in range(start, start+term):
            dp(start)(start+term) = min(dp(start)(start+term),
                                        # 👇 1 + 2 + 3
                                        dp(start)





끝!


    

  • 시작행렬부터 마지막행렬까지의 최소연산횟수를 반환합니다.

    print(dp(0)(N-1))
    

    • 





전체 코드


import sys
N = int(input())
arr = (list(map(int, sys.stdin.readline().split())) for _ in range(N))

dp = ((0)*(N) for _ in range(N))

for term in range(1, N):
    for start in range(N):  # 첫행렬 : i, 끝행렬: i+term
        if start + term == N:  # 범위를 벗어나면 무시
            break

        dp(start)(start+term) = int(1e9)  # 지금 계산할 첫행렬과 끝행렬

        for t in range(start, start+term):
            dp(start)(start+term) = min(dp(start)(start+term),
                                        # 👇 1 + 2 + 3
                                        dp(start)

print(dp(0)(N-1))