[BOJ] C++ 1629 곱셈 - 귀납적 사고와 재귀 함수 구조 연습하기

1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 예제 10 11 12 ans : 4 a^b mod c를 구하는 문제이다. 가장 간단하게 생각할 수 있는 방법은 a^b을 구하고 mod c를 구하는 방법이다. 하지만 a, b, c 숫자가 모두 크기에 오버플로우도 나고, 시간초과도 뜬다. 오버플로우를 해결할 수 있는 방법은 long long 타입을 쓰면서 (a mod c)^b를 구하는 방식으로 해결할 수 있다. 이 방법은 O(b)만큼의 시간이 걸린다. 그러나 b의 크기는 매우 커서 또 시간 초과가 뜬다. 이 문제는 다음의 방법을 통해 귀납적 사고를 해서 재귀 구조로 구현하여 풀 ..

2023.09.12