문제 10830번

소스코드

풀이 접근

1. 먼저 행렬 곱에 대해서 생각한다 i,j,k순으로 3중 for문을 돌린다고 했을 때 (i,j) 좌표에는 (i,0~k) * (0~k,j)의 합이 들어간다.
   ex)
2. 문제에서 행열의 크기는 최대 5x5 밖에 안 되지만, 제곱수를 보면 B가 1000000000000까지 가능하기 때문에 그냥 단순 식으로 만들면 100% 시간이 오래 걸릴 것이다.
3. 위의 문제점을 해결하기 위해 분할정복을 구현하기로 했다.
4. 재귀적인 OddorNot이라는 메소드를 구현하였다.
   해당 메소드는 2의 제곱 단위로 계산하기 위해 구현한 방법이다.
   ex) 2^17 이라면 2^16(2^8 x 2^8)x 2^1 이런 식으로 2의 제곱 단위로 분할하여 계산된다.
5. 이렇게 나온 값을 출력한다.

문제 핵심

• 행렬 제곱에 대한 이해
• 분할 정복 방법 구현