11049번 - 행렬 곱셈 순서
행렬 곱셈 순서 정할 때 모든 경우의 수의 곱셈 횟수를 다 구하고 그 값 중에 최소값을 구하는 방식으로 문제를 해결하고 싶은데 방법이 생각나질 않습니다. 재귀로 해야 할까요? 모든 경우의 수 구할 때 어떤 방식으로 접근해야 할까요?
가장 생각하기 쉬운 방법은 백트래킹으로 현재 가능한 모든 인접한 행렬 중 하나를 골라, 실제로 합쳐주시면 될 것 같습니다.
ex) (5,3) (3,2) (2,6) -> (5,3) (3,6) -> (5,6)
물론 제한시간 내에 동작하진 않습니다.
댓글을 작성하려면 로그인해야 합니다.
tmdgks49 2년 전
행렬 곱셈 순서 정할 때 모든 경우의 수의 곱셈 횟수를 다 구하고 그 값 중에 최소값을 구하는 방식으로 문제를 해결하고 싶은데 방법이 생각나질 않습니다. 재귀로 해야 할까요? 모든 경우의 수 구할 때 어떤 방식으로 접근해야 할까요?