Stargazer

접근: DP(Dynamic Programming)을 이용해서 푸는 문제. 발상은 행렬 곱셈이 이루어진 후에 두 행렬이 하나의 행렬로 이루어지기 때문에 작은 문제를 뭉쳐서 큰 문제를 해결 할 수 있음을 암시한다. 전략: 전체 행렬의 곱을 큰 문제로 보았을 때, 두 행렬의 곱으로 나눌 수 있고(구간 단위로), 이는 작은 문제로 나누어서 해결한다는 뜻이다. 그 행렬을 구할 수 있는 모든 경우의 수 중에 가장 연산이 가장 작으려면, 구간을 어떻게 나누었을 때 가장 곱 연산이 작은 지를 알면된다. 따라서 구간을 잘게 쪼개어 DP적으로 해결한다. 맨 아래(기본 행렬 곱)에 도달 했을 때, 두 행렬의 곱 연산 수를 구하여서 그 값을 저장한다. 이를 쌓아서 올리면 전체 곱셈 순서를 구할 수 있게 된다. -> 행렬을 나..