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

처음에 보고 먼소린가 했는데 행렬의 곱셈이 이루어진 후의 연산 비용을 계산해보는 문제이다. 따라서 최소값을 구하면 된다.

그럼 식을 세워야 한다. 저번에 풀었던 11066문제와 비슷하다. 양옆으로 연산을 하기 때문에 잘 쪼개서 계산하면 된다.

그래서 일반항으로 나타내면 아래와 같다.

아주 다행인건 최적화 따위를 안해도 된다는 것이다.

여기서 팁은 최솟값이 적어도 2^31-1보다 작아야한다는 것이다. 따라서 이부분을 놓치지 않고 코딩으로 바꾸어 주면 아래와 같다.

n = int(input())
p = []
for i in range(n):
    p.append(tuple(map(int, input().split())))
D = [[0 for i in range(n)] for i in range(n)]
# 연산시작
for dig in range(n-1):
    for i in range(n-1-dig):
        j = i + 1 + dig
        # min구하기
        D[i][j] = 2 ** 32
        for k in range(i, j):
            D[i][j] = min(D[i][j], D[i][k] + D[k+1][j] + p[i][0]*p[k][1]*p[j][1])
print(D[0][n-1])

pypy3로 제출해서 통과하였다.

DP은근히 조금 실력이 늘은듯?!!ㅎㅎ