사용자 도구

사이트 도구


ps:problems:boj:11049

행렬 곱셈 순서

ps
링크acmicpc.net/…
출처BOJ
문제 번호11049
문제명행렬 곱셈 순서
레벨골드 3
분류

동적 계획법

시간복잡도O(n^3) ( Optimal: O(nlogn) )
인풋사이즈n<=500
사용한 언어Python
제출기록34452KB / 4056ms
최고기록4056ms
해결날짜2021/03/02

풀이

  • 유명한 DP 문제인 행렬 연쇄 곱셈 문제이다.
  • n<500이라는 제한 조건은 옵티멀한 O(nlogn)풀이 대신에 O(n^3)으로도 통과되도록 의도한 것 같지만, Python으로 시간 안에 통과하려면 마이크로 최적화가 필요하다. 자세한 것은 행렬 연쇄 곱셈 참조.
  • 동일한 구현을, 좀더 가독성있게 작성한 코드는 최적의 연쇄 행렬을 참고. 동일한 문제지만 n<200 이어서 쉽게 통과된다.

코드

"""Solution code for "BOJ 11049. 행렬 곱셈 순서".

- Problem link: https://www.acmicpc.net/problem/11049
- Solution link: http://www.teferi.net/ps/problems/boj/11049
"""

import sys


def main():
    n = int(sys.stdin.readline())
    r_and_c = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)]

    sizes = [r for r, _ in r_and_c]
    sizes.append(r_and_c[-1][1])
    dp = [[0] * n for _ in range(n)]
    for l in range(1, n):
        for i in range(n - l):
            j = i + l
            sz_ij = sizes[i] * sizes[j + 1]
            m = min(min_ik + min_kj + sz_ij * sz_k for min_ik, min_kj, sz_k in
                    zip(dp[i][i:j], dp[j][i + 1:j + 1], sizes[i + 1:j + 1]))
            dp[i][j] = dp[j][i] = m

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


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
L X O᠎ W K
 
ps/problems/boj/11049.txt · 마지막으로 수정됨: 2021/03/11 04:46 저자 teferi