백준 11049 - 행렬 곱셈 순서

 

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

 

import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    matrix = []
    for _ in range(N):
        matrix.append(list(map(int, input().split())))

    # dp[i][j] : i번째 행렬부터 j번째 행렬까지 곱했을 때의 최소 곱셈 연산 횟수
    dp = [[0] * N for _ in range(N)]

    # term: 구하려는 구간의 크기 (몇 개의 행렬을 묶을 것인가)
    # 1개 차이(인접한 두 행렬)부터 N-1개 차이(전체)까지 반복
    for term in range(1, N):
        for i in range(N - term):  # 시작 행렬 인덱스
            j = i + term           # 끝 행렬 인덱스
            
            # 초기값을 무한대로 설정
            dp[i][j] = float('inf')
            
            # k: i와 j 사이의 분할 지점 (i <= k < j), k는 결합법칙 구현위한 괄호역할
            # (i~k) 덩어리와 (k+1~j) 덩어리로 나누어 계산
            for k in range(i, j):
                # 비용 = 왼쪽 덩어리 비용 + 오른쪽 덩어리 비용 + 두 덩어리를 곱하는 비용
                # matrix[i][0]: 첫 행렬의 행
                # matrix[k][1]: 왼쪽 덩어리의 마지막 행렬의 열 (== 오른쪽 덩어리 첫 행렬의 행)
                # matrix[j][1]: 마지막 행렬의 열
                # ABC 행렬 곱셈 예시:
                # dp[i][k]: A*B 곱셈 비용 -> (A*B)와 같음 -> Tmp
                # dp[k+1][j]: C 곱셈 비용
                # matrix[i][0] * matrix[k][1] * matrix[j][1]: (Tmp)*C 곱셈
                cost = dp[i][k] + dp[k+1][j] + matrix[i][0] * matrix[k][1] * matrix[j][1]
                
                if cost < dp[i][j]:
                    dp[i][j] = cost

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

solve()

 

문제 풀다 ㄹㅇ 벽느낌... 아니 내가 점화식을 이해 못하는건지... 행렬 곱셈 이해를 못하는건지 모를 정도로 멘탈 바사삭이다.. 간만에 행렬의 교환법칙, 결합법칙 찾아보기도 했는데 ㄹㅇ 펜이면 펜, 노트면 노트, 노트북이면 노트북 다 던질뻔... 골3 너란 새끼 왤케 어려운거냐... 하 진짜 내가 왜 이 고생을 하는건지 ㅜㅜ

 

예.. 사실 제미나이가 풀어줬습니다 ㅜㅜ

 

줜나게 어려워서 이해를 못했지만 지금도 아오.. 반드시 해결해본다