11049번 행렬 곱셈 순서

Problem link: https://www.acmicpc.net/problem/11049

Keywords: Dynamic programming

뭐 그저 그런 DP 겠거니하고 몹시 교만하게 접근하였으나 의외로 고전했다. Recursive DP solution 까지는 꽤나 빨리 떠올렸는데, iterative DP solution 은 찾지 못해서 조금 아쉬웠다.

Recursive DP solution 은 아래와 같다.

• CACHE[i][j] : i 번 행렬부터 j 번 행렬까지 곱할 때 필요한 곱셈 수의 최솟값
• CACHE[i][j] = min(CACHE[i][k] + CACHE[k+1][j] + 두 덩어리(?)를 곱하는데 필요한 곱셈 수) (단, k < j)

위와 같이 정의하면 별 탈 없이 풀린다. 그런데, 문제는 이것을 iterative DP solution 으로 스스로 바꾸지 못했다는 것인데…ㅠㅠ. DP 테이블을 어떤 순서로 채워야하는지 감을 못잡아서 그랬다. 필자는 멍청하게 계속 row-major 로 채워넣으면서 “음…미래의 값에 의존하는데…어쩌지” 하고 있었다. 그런데, 알고보니 diagonal 방향으로 순서대로 채워넣으면 해결할 수 있었다. 이것은 필자의 설명보단 이 블로그 포스팅 이 잘 설명하니 참고하기 바란다.

솔루션은 여기 에서 확인할 수 있다.