[11049번] 행렬 곱셈 순서 (행렬 곱 연산 횟수의 최솟값 구하기, DP)

2023. 4. 4. 11:22·Coding Test/DP
728x90
 

11049번: 행렬 곱셈 순서

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

www.acmicpc.net

 

 

분석

 

풀이

import sys
imput=sys.stdin.readline

# 행렬의 갯수
n=int(input())
# 행렬
m=[]
# 최소 연산 횟수 저장 리스트
d=[[-1 for j in range(n+1)] for i in range(n+1)]

m.append((0,0))

for _ in range(n):
    x,y=map(int, input().split())
    m.append((x,y))

def execute(s,e):
    result=sys.maxsize

    if d[s][e] != -1: # 이미 계산
        return d[s][e]
    if s==e: # 행렬 1개
        return 0
    if s+1==e: # 행렬 2개
        return m[s][0]*m[s][1]*m[e][1]

    for i in range(s,e):
        result=min(result, m[s][0] * m[i][1] * m[e][1] + execute(s,i) + execute(i+1,e))
    d[s][e]=result
    return d[s][e]


print(execute(1,n))

 

 

 

728x90
저작자표시 (새창열림)
'Coding Test/DP' 카테고리의 다른 글
  • [12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색)
  • [2098번] 외판원 순회(TSP, 비트 마스킹)
  • [9252번] 최장 공통 부분 수열 찾기(LCS)
  • [2193번] 이친수 구하기
Karla Ko
Karla Ko
𝘾𝙤𝙣𝙩𝙞𝙣𝙪𝙤𝙪𝙨𝙡𝙮 𝙄𝙢𝙥𝙧𝙤𝙫𝙞𝙣𝙜, 𝘾𝙤𝙣𝙨𝙩𝙖𝙣𝙩𝙡𝙮 𝘿𝙚𝙫𝙚𝙡𝙤𝙥𝙞𝙣𝙜 𝙔𝙚𝙨!
    250x250
  • Karla Ko
    karlaLog
    Karla Ko
  • 전체
    오늘
    어제
    • Total (467)
      • Spring (19)
      • JPA (4)
      • Cloud & Architecture (15)
        • Kubernetes (5)
        • Docker (3)
        • MSA (2)
        • GCP (1)
        • AWS (4)
      • Devops (1)
      • Message Queue (4)
        • Kafka (2)
        • RabbitMQ (2)
      • Git (4)
      • DB (4)
      • Java (9)
      • Python (4)
      • CS (11)
        • OS (8)
        • Network (2)
        • Algorithm (1)
      • Coding Test (392)
        • programmers (156)
        • Graph (43)
        • DP (37)
        • Search (31)
        • Tree (13)
        • Data Structure (26)
        • Combination (12)
        • Implement (18)
        • Geedy (23)
        • Sort (7)
        • Math (21)
        • geometry (2)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    그리디
    큐
    자료구조
    최단거리
    프로그래머스
    DP
    Algorithm
    이분탐색
    최대공약수
    알고리즘
    정렬
    백준
    힙
    스택
    파이썬
    LIS
    최소신장트리
    구간합
    덱
    조합
    다익스트라
    플로이드워셜
    트리
    재귀
    그래프
    BFS
    구현
    DFS
    동적계획법
    월간코드챌린지
  • hELLO· Designed By정상우.v4.10.3
Karla Ko
[11049번] 행렬 곱셈 순서 (행렬 곱 연산 횟수의 최솟값 구하기, DP)
상단으로

티스토리툴바