목록알고리즘/백준 (1)

코딩하는 오리

[백준] 11049_행렬 곱셈 순서 (java)

https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제를 읽어보고 바로 DP문제라는 사실을 알아내지 못했다. 처음에는 어떤 두 행렬을 먼저 곱할지 순서를 순열을 통해서 확인하는 순열(완전 탐색)을 생각했다. 그러나 최대 499!은 말도 안되는 비교 횟수이기에 다른 방법으로 해결해야했다. DP를 적용하기 위해서는 점화식을 잘 세워야 한다. 이전 값을 중복해서 잘 사용할 수 있어야 한다. 문제에서 N은 최대 500이지만 N을 3으로 줄여..
알고리즘/백준 2023. 1. 13. 17:45
이전 Prev 1 Next 다음