[BOJ] 11049. 행렬 곱셈 순서 (python, DP, 그림풀이)

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

11049번: 행렬 곱셈 순서

 

 

 

이 문제를 풀 때, 고민한 부분들이 있는데

 

1. A와 B를 계산하고 난 후에, 계산한 행렬이 변형이 되는데( ex. A(5,3) * B(3,2) -> (5*2) 
   이 변형된 행렬을 어떻게 저장하고 계산해야 할지
2. 1번 전제에서부터 DP테이블을 어떻게 구현해야 하는지, 값을 어떻게 저장해야하는지

위 질문들을 던져보았고, 1번과 2번을 풀이과정을 통해 이해하게 되었다.

정말 단순 이해만 하게 되었고, 이걸 응용하라고 하면 정말 엄두가 안날 것 같다.

밑에 실행과정들을 그림으로 표현해보았는데, 어떻게 저 플로우를 적용해서 문제를 풀 생각을 했을까 라는

감탄 밖에 안나온다.

 

이 문제가 저번에 정리한 11066번째 문제에서 나오는 조합과 관련되어 유사한 과정이 있는데,

그것은 포인터와 같은 간격변수를 두고 대각선으로 값들을 구해놓고, 내부로 파고들면서 외각의 데이터들을 누적합산하면서 구하는

테크닉이 있는 것 같다. 두 문제 전부 조합과 관련된 문제인데, 이런 테크닉이 쓰이는 걸 보니,

조합을 이용한 DP의 풀이과정이 머릿속에 그림이 그려지긴 하는데.. 그래도 .. 어렵다

  

def matrix_chain_multiplication(N, matrices):
    # dp[i][j]는 i번째 행렬부터 j번째 행렬까지의 최소 곱셈 연산 횟수를 저장합니다.
    dp = [[0] * N for _ in range(N)]

    # point는 현재 고려하고 있는 행렬들의 간격을 나타냅니다.
    for point in range(1, N):
        # left는 현재 고려하고 있는 행렬들의 시작 인덱스를 나타냅니다.
        for left in range(N - point):
            # right는 현재 고려하고 있는 행렬들의 마지막 인덱스를 나타냅니다.
            right = left + point

            # tmp는 left부터 right까지의 행렬들을 곱하는데 필요한 최소 연산 횟수를 저장합니다.
            tmp = float('inf')
            # mid는 left와 right 사이에서 행렬 곱셈을 분리할 위치를 나타냅니다.
            for mid in range(left, right):
                # 현재 위치에서의 최소 연산 횟수를 계산합니다.
                tmp = min(tmp, dp[left][mid] + dp[mid + 1][right] + matrices[left][0] * matrices[mid][1] * matrices[right][1])

            # 최소 연산 횟수를 dp 테이블에 저장합니다.
            dp[left][right] = tmp

    # 전체 행렬을 곱하는데 필요한 최소 연산 횟수를 반환합니다.
    print(dp[0][-1])
    return dp[0][-1]


N = int(input())
matrices = [list(map(int, input().split())) for i in range(N)]
matrix_chain_multiplication(N, matrices)

 

 

DP문제를 풀다가 나만의 팁이 생겼다

시간을 30분으로 제한해놓고 이 문제를 어떻게 풀지 수도코드 아니면 디스크립트 정도로만 정리한다

그리고 30분 지나고 내가 끄적인거 보고 코드로 옮길 수 있을 것 같다 싶으면 도전해보고

안되면 해설보는게 맞는 것 같다. 

DP는 내가 오기를 부려 풀 수 있는 문제가 아닌 것 같다

시뮬레이션,BFS,DFS 이런 구현문제들은 몇일 지나서 고민해 풀어본 경험이 있는데

DP는 내가 고민한 모든 걸 뒤엎어야 한다

그래서 DP문제를 풀때마다 스트레스가 이만저만이 아니다

내가 이정도 밖에 안되나? 싶을 때가 있는데

정신건강 + 효율면에서 DP는 욕심부리지 말고 놓아주고 내 자신을 이해해야 한다.

아 나는, 이 문제를 모르는구나.

특히 DP문제를 풀 때, 심각한 부분은 풀이를 보더라도 아! 이렇게 풀어야 하는구나 가 아닌

이게 왜 이렇게 되는거야? 하고 한참을 뜯어보고 순서를 그려봐야 이해가 된다

즉 풀이보고 그 풀이과정을 이해하는데에도 시간이 너무 많이 걸리는데

문제 푼다고 몇시간 머리 싸매놓고, 문제 풀이는 또 문제풀이대로 머리를 싸매니

더 기피하게 되고 멀어지는 것 같다.