https:acmicpc.net/problem/11245
-------------스포------------------
분할정복 없이 그냥 갈겨도 시간복잡도가 괜찮은 것 같은데 왜 분할정복으로 풀 수 있는 건지 그 자체를 모르겠음. 뭔가 수학적인 증명이 필요한 건가?
-------------스포------------------
분할정복 없이 그냥 갈겨도 시간복잡도가 괜찮은 것 같은데 왜 분할정복으로 풀 수 있는 건지 그 자체를 모르겠음. 뭔가 수학적인 증명이 필요한 건가?
직관적으로는 3중 for loop 돌면서 모든 경로의 값을 체크하고 가기 때문에 graph theory에서 adjacency matrix를 exponentiation하는 것과 비슷하게 성립할 것 같은데 맞는 지 모르겠다
아 모든 경로가 아니라 경우의 수
링크 잘못 단 것 같은데
문제 번호 잘못 달았더라 수정했어
태국어 문제도 있구나