백준 11049 풀이/코드(파이썬), 골드3 다이나믹 프로그래밍 문제

코드만 궁금한 분은 깃허브 링크 눌러주세요! :)

GitHub - Rhyankwon/algorithms

 

문제는 여기

11049번: 행렬 곱셈 순서

문제 설명을 간략하게 하자면

행렬의 경우 분배 법칙..이라고 해야하나? 아무렇게나 막 곱해도 값이 똑같은 그런 규칙이 적용되지 않아서 곱셈 순서에 따라 값이 상당히 달라진다. 그래서 그 규칙을 적용했을때의 최소값을 구하라는 문제이다. dp를 활용하는 문제.

 

 

 

 

문제 해결 논리

 

- 만일 행렬 4개가 있다면 0, 1, 2, 3라고 할 수 있겠다. dp[A][B]는 A부터 B까지 곱했을 때의 최솟값이다. 가령,

 

dp[0][3]은 dp[0][0]과 dp[1][3]의 조합 혹은 dp[0][1], dp[2][3]의 조합 혹은 dp[0][2]와 dp[3][3]의 조합 중 최솟값이다.

 

dp[0][1]과 dp[2][3]의 조합의 경우에는 각각 0째 1째 행렬을 곱한것과 2째 3째 행렬을 이미 곱한 값이 들어있으므로 두 값의 합에다가 [0째 행렬의 행 * 1째 행렬의 열 * 3째 행렬의 열] 값을 더하면 된다. 

 

이는 dp[0][3]의 경우에만 해당하는거고, 이런 식으로 dp[0][1]~... 전부 모든 값을 하면 된다. 이 때 행렬은 대각선으로 채워지게 된다. 0-1, 1-2, 2-3 까지 근접한 행렬끼리 먼저 계산해야하기 때문이다.

 

 

 

나도 내가 먼저 혼자서 답안을 생각해내진 못해서 구글링으로 풀이를 보고 풀었다. 처음에 코드만 보고는무슨말인지 도통 이해가 안됐는데, 먼저 풀이 논리를 생각해보고 구현해보니까 오히려 똑같은 답안이 나왔다. 이게 dp의 매력이랄까.. 그냥 점화식 세워서 꾸역꾸역 푸는거.ㅋㅋㅋ 다음에 꼭 다시 혼자 풀어봐야겠다. dp는 풀기 전에는 도통 감이 안오는데 막상 풀고 보면 이런걸 왜 생각 못했지? 싶은게 참 많다.