알고리즘 (PS)/BOJ
[백준] 12850 - 본대 산책 2 (G1)
https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 처음엔 그림만 보고 그래프 문제를 예상했는데, 문제를 읽어보니 경우의 수를 세라길래 DP로 예상해서 DP 점화식을 세웠다. 근데 dp테이블을 일일히 채우고 있다가는 저 10억이라는 입력데이터를 감당하지 못하겠다는 생각이 들었다. 그래서 결국 알고리즘 분류를 봤다.. 그런데 띠용.. '분할정복을 이용한 거듭제곱' 문제라고 소개가 되어있었다. 다행히 이걸 보고 전에 풀었던 피보나치 문제가 스쳐지나갔다. 행렬 거듭제곱을 이용해서 피보나치 수열을 빠르게 구하는 문제였다. 그런데 부끄럽게도 그 문제를 풀 당시에는 피보나치..
