재귀 (1) 썸네일형 리스트형 백준 1629번 곱셈 문제 설명 문제를 분석해보면 A의 B제곱을 C로 나눈 나머지는 A의 B/2제곱을 C로 나눈 나머지를 알면 알 수 있다. 이 뜻은 K제곱을 계산했으면 2K제곱과 2K+1제곱을 계산할 수 있다는 뜻이다. 그래서 B가 1이면 A % C를 리턴하고 그렇지 않으면 B를 2로 나눈 값을 인자로 넣어 재귀함수를 실행한다. 전체 코드 def func(a,b,c): if b == 1: return a % c val = func(a,b//2,c) val = val * val % c if b % 2 == 0: return val else: return val * a % c def main(): li = list(map(int,input().split())) print(func(li[0],li[1],li[2])) 이전 1 다음
