유령이 나오는 젤리하우스

Algorithm/Baekjoon

[BOJ 1629][백준 1629번] 곱셈 (파이썬 풀이)

https://www.acmicpc.net/problem/1629 🤔 문제 설명 및 입출력 ✍ 접근 방법 눈에 보이는대로 풀면 이렇게 쉬운 문제가 없다. 그냥 A*B%C 하면 되는 문제니까 말이다. 근데 정답률을 보아하니 나처럼 생각했다간 큰 코 다치는 문제임이 확실하다. 괜히 S1 난이도를 단게 아닌거 같다. 그래서 구글링을 좀 해보니, O(N) 곱셈을 O(logN)으로 줄여주는 방법인, 분할정복을 이용한 방법으로 해결해야한다고 한다. 단순 곱셈에 어떻게 분할 정복을 적용하나 싶었는데, 생각보다 간단한 아이디어였다. 2^8 계산을 해야한다 해보자. 여태까지 우리는 컴퓨터에게 2*2*2*2*2*2*2*2 를 시켰다. 근데 이 식을 잘 살펴보자. 2^8은 2^4 * 2^4 가 아니던가??? 그럼 2^8 =..