1629번: 곱셈 (파이썬, 풀이, 정답 코드)

1629번: 곱셈 (acmicpc.net)

1629번: 곱셈

매우 간단한 문제이다. 그냥 A의 B제곱을 C로 나눠서 반환하면 되기 때문이다. 그러나 입력 제한을 보면 B 역시 int(2147483647) 최대값까지 들어갈 수 있기에 단순하게 B제곱을 했다가는 어마무시한 시간 초과가 나버리게 된다. 
이를 조금 완화하는 방법이 있는데, 조금의 수학 지식이 필요하다. 

나머지 분배 법칙

(A * B) % C = (A%C) *(B%C) % C

대충 이런 법칙이 있다. 간단하게 말하자면 두 수를 곱한 것의 나머지를 구할 때는, 각각의 나머지를 먼저 구하고 그걸 곱한 뒤에 나머지를 구해도 된다는 것이다. 이것을 이용해 우리는 우리가 구하려는 어마무시하게 조각 내서 나머지를 구하는 전략을 취할 수 있다.
이 문제를 이 법칙을 통해 접근하려면, $A^16$이라면 이를 반으로 쪼개서 $A^8$ 두 개로 만들고, 이를 또 쪼개서 $A^4$ 두 개로 만드는 식으로 해서 각각을 나머지 분배를 하면 된다.

분할정복

그래서 만들어지는 방식이 어떻게 되느냐, 단순하다. 이를 나중에 정리하려고 찾아보니까 분할정복이라고 부르던데, 딱히 그것을 의식하고 있지는 않았지만 중요한 개념인 것 같아서 적는다. 
분할정복이란 큰 문제를 작은 문제로 나눠서 정복하는 것을 말한다. 쪼개고, 그 쪼갠 것을 또 쪼개고, 무한 반복.. 하면 큰 수라도 쉽게 작게 만들어낼 수 있다. 가령 쪼개는 것을 반으로 쪼갠다치면, 64란 숫자는 6번의 과정만에 1까지 쪼개질 것이다. 이를 $\log(n)$만큼의 시간이 들어간다고 보통 이야기한다. $64 = 2^6$인데 이때 6이라는 지수에 해당하는 만큼으로 시간이 줄었기 때문이다.
나는 이러한 방식을 이용하지 않으면 시간초과가 날 것이란 것을 알고 있었기에 분할정복을 통해 문제를 해결해보려 했다.

def recur(x,y,z):
	if y== 1:
		return x % z
	elif y == 2:
		return x ** y % z

	if tmp[y] != -1:
		return tmp[y]
	tmp[y] = recur(x, y//2, z) * recur(x, y- y//2, z) % z
	return tmp[y]

처음에 만든 방식은 바로 이것이다. dp를 곁들여서, 재귀를 계속 돌 때 반복되는 값에 대한 재귀를 돌지 않도록 만들었다. 참고로 이렇게 dp를 쓰지 않으면 시간 초과가 난다. 
그런데 이것도 문제가 있었으니.. 바로 메모리 초과가 난다는 것이었다. tmp자료형을 처음에는 리스트로 했다가, 안 돼서 딕트로 했다가 여러가지 조작거려봤는데, 어떻게 해도 메모리 초과가 났다. 이러한 풀이를 하게 된다면 우리에게 입력으로 들어오는 지수 값의 크기를 가진 배열을 선언하게 되는데, 이것에서 이미 너무나도 큰 메모리를 요구하게 되는 것이라 그 부분에서 문제가 발생하는 것으로 보였다.

정답 코드 

a,b,c = map(int, input().split())

def recur(n):
	if n == 1: return a % c
	tmp = recur(n//2)
	if n % 2: return tmp * tmp * a % c
	else: return tmp * tmp % c

print(recur(b))

결과적으로 더 공부를 한 뒤에 만들어낸 코드. 재귀를 돈다는 것도 같고, 나머지 분배 법칙을 쓰는 것도 같다. 그런데 dp를 사용하지 않고 푸는 방식이다. 이러면 위에서 우려했던 반복되는 값에 대한 중복 재귀가 들어가는 것이 문제가 될 법한데, 막상 코드를 제출하니 조금의 문제도 없었다. 아무래도 분할정복이 가진 위력이라고도 볼 수 있을 것 같다. 아무리 큰 문제라고 할 지라도 그것을 로그 수준의 복잡도로 낮춰버리면 굉장히 작은 값이 된다. 

추가

a,b,c = map(int, input().split())
print(pow(a,b,c))

pow라는 함수를 쓰면 그냥 2줄로도 코드를 짤 수 있다! pow 자체가 제곱 연산을 해주는 함수인데 뒤에 인자를 하나 더 넣으면 나머지 연산을 해준다. 
이런 내장 함수를 잘 알고 있는 것도 코테에서 시간을 단축하는 핵심이다. 꼭 기억해두자!