[BaekJoon/백준] 2740 분할정복이지만...

이 문제를 분할정복으로 풀어가려면 '슈트라센 알고리즘'을 사용해야한다.

일단 2740번은 분할정복 카테고리에 해당하는 문제다.

"행렬의 곱셈을 어떻게 분할정복으로 풀어나갈 수 있을까...?" 라는 고민을 했다.

그리고 도저히 알 수 없어서 풀이를 검색했는데, 진짜 너무나도 많은 사람들이

분할정복이라고 해놓고, 3중포문으로만 구현한 풀이를 자신있게 내놓았다....

뭐지..?

행렬곱셈을 이용해 3중포문으로 푸는건 알겠는데, 이건 분할정복이 아니니까

계속해서 풀이를 찾아봤는데도 다들 '분할정복' 이라고 떡하니 써놓고 3중포문으로 구현한 행렬곱셈을 내놓았다..

나도 분할정복이라는 알고리즘의 정의나 개념을 제대로 이해하진 못했겠지만, 이런 풀이가 분할정복이 아니라는 건

너무나도 잘 알겠는데,,..

이 문제를 슈트라센 알고리즘을 적용하여 푼 풀이를 아직까지 못찾았다.. 그걸 보고 공부한 뒤 포스팅을 하려고 했는데ㅜㅜ

슈트라센 알고리즘 구현이 자체적으로 어렵기도 한 부분인 것 같다.

어쨌든, 이 문제는 문제의 시간 조건상 행렬곱셈을 3중포문으로 구현해서도 풀 수도 있지만

분할정복으로 풀어가려면 슈트라센 알고리즘이라는 것을 쓰는게 맞다.

알고리즘의 이해력이 개인적으로 부족하다고 생각했는데, 죄송한 말씀이지만 검색을 하면서 다른 분들의 포스팅을 보고 많은 힘을 얻었다..

분할정복 풀이를 기대하고 찾아오신 분들이라면 죄송하지만..

도저히 분할정복으로 풀 수가 없겠어서, 나도 일단 간단하게 3중 포문으로 구현했다. 나중에 더 찾아보고 구현해볼 생각이다!!

시간복잡도가 매우 크다.

이 문제는 숫자의 범위가 그렇게 크지 않고, 시간도 넉넉해서 이렇게 풀 수도 있겠지만

더 큰 범위나 짧은 시간에서 슈트라센 알고리즘을 이용하면 분할정복으로 더 빨리 풀 수 있다.

+ 참고 자료

행렬 곱셈 자료(위 풀이에 대한 참고자료) : ko.wikipedia.org/wiki/행렬_곱셈

슈트라센 알고리즘에 대한 설명(구현이 빡센 듯 하다)

관련글