[BOJ][Python]1629번 풀이

https://www.acmicpc.net/problem/1629

1629번: 곱셈

def sol(a,b,c):
    if b == 1:
        return a%c
    elif b%2 == 0:
        return (sol(a,b//2,c)**2)%c
    else:
        return (sol(a,b//2,c)**2)*a%c

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

요즘 갈수록 풀이를 안보고 못푸는 문제가 늘어나는 것 같습니다. 해당 문제는 그 성격이 조금 다르긴 합니다만 풀이를 본 건 같으니까요. 풀이를 보고도 계속 다른 방법으로 해보려고 했는데 도저히 안풀리더라구요. 어떤 방법을 썼는지 왜 안되는지에 대한 제 추측까지 함께 작성해보겠습니다.

 

문제 접근 방법은 분할 정복이라고 하네요. 사실 어떻게든 반복수를 줄여야하긴 했습니다. 그냥 시키는대로 했다간 b가 최대값인 21억이 나올 때 그걸 그대로 21억번 곱하고 있을테니 당연히 시간초과가 날 것입니다. 그래서 그 반복 횟수를 줄여야 하는데 제가 찾았던 풀이에서는 위와 같은 방법을 사용하고 있습니다. 예를 들면 2^8 = 256이지만 4^4 = 256이죠. 16^2 또한 256입니다. 위 풀이는 이런식으로 b를 줄이는 방법을 이용해서 시간복잡도를 떨어트리는 방법을 이용하고 있습니다. O(log(n)) 정도 될 것 같네요. 다만 해당 방법의 신기한 점은 return이 a%c, 즉 나머지인데 나머지에 제곱을 하고 다시 c로 나눈 나머지를 출력해도 값이 전혀 바뀌지 않는 점이 저는 신기했습니다. 이게 아마 중학교나 초등학교 수학책을 다시 찾아보면 해당 내용이 있을 것 같은데 저는 기억이 안났는지 몰랐는지 몰랐기 때문에 아마 제 풀이를 완성할 수 없었던 것 같습니다.

 

저는 일반적인 반복문을 사용하긴 했습니다. 다만 위와 좀 달랐던 점은 a도 키우고 b는 낮추는 방식을 썼습니다. 예시 1을 이용해보면 10 11 12 ==> 100 5(1) 12 ==>... 이런 식으로 해결을 하려고 했는데 문제를 풀지 못했었죠. 시간초과가 났던 이유를 추측해보자면 일단 a가 너무 커진다는 점이 있습니다. 예를 들어서 테스트 케이스의 처음부터 a의 최댓값인 21억을 준다면 문제가 있겠죠. b가 4 정도만 되어도 끔찍해질겁니다. 그 정도로 숫자가 커진 상태에서 승의 연산을 한다면 무슨 문젠진 몰라도 뭔가 문제가 생기긴 생기겠죠. 이것과 관련해서 나머지를 제곱하고 나머지를 구하더라도 같은 값이 나온다는 사실을 몰랐던게 또 하나의 이유일 것 같습니다. 어렵다면 어려운 문제였지만 또 새로운 걸 배웠으니 기분은 좋네요.