[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 == 2^4 * 2^4 이다. 어라?? 가만히 보니까  2^4도 2^2 * 2^2 아닌가???

 

그럼 2^8 == (2^2*2^2) * (2^2*2^2)이다. 어라??? 가만히 보니까 2^2 도 2^1*2^1 아닌가???

 

 

뭔가 자기 자신을 반으로 쪼개는 식이 반복되는데...??

 

자기자신이 반복....base case 있음.....이거 완전....???

 

 

띠요요요용  

 

 

반으로 쪼개는 분할과정을 재귀함수로 구현하면 낙승이다.

 

단 여기서 주의할 점은, 지수가 2로 딱 떨어지지 않았을 경우이다. 즉, 2^5 == (2^2*2^2)*2 인 경우인데, 이때는 반으로 쪼갠 값을 돌려주기 전에, 지수를 한번 곱해주자. 

 

 

 

👨‍💻 소스 코드

---

• 파이썬

 

def pow(a,b,c):
    if b == 1:
        return a % c
    
    n = pow(a,b//2,c)
    temp = n * n # n을 재귀형으로 구하기 때문에, temp은 n이 구해진 뒤 나온다.
    if b%2 == 0:
        return temp % c
    else:
        return a * temp % c


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

ans = pow(a,b,c)
print(ans)

 

매 return 마다 %c로 나눠줘야함을 주의해야한다.

 

나는 처음에 a^b %c를 해줘서 나머지를 한번에 구하려고 했는데, 이러면 시간 초과가 난다.

 

어떻게 보면 당연하다. a^b이 엄청 큰 숫자가 되서 그 큰 수의 연산을 빠르게 하려고 이렇게 분할 정복을 한건데, 나누는 과정도 분할정복이 들어가지 않으면 도로묵이 되는거 아니겠는가? 그렇기 때문에 매 return 마다 % c를 해줘서 속도를 확보하자. 분배법칙에 따라, 이렇게 중간중간 %c를 해줘도 결과에는 변함이 없다.

 

 

🔥 강평

---

마일스톤 달성

 

이번 문제를 해결함으로서 드디어 백준 골드티어에 도달할 수 있었다.

 

롤도 골드를 달아본적 없는 내가 알고리즘 풀이에서 골드 티어가 됬다고 생각하니 진짜 감회가 새롭고 스스로가 대견스럽다.

 

목표했던 골드 티어도 달았으니, 이제부터는 한결 편안한 마음으로 내가 부족하다고 생각되는 영역 문제만 집중적으로 풀어봐야겠다. 사실 이전까지는 티어 올리는데에 집착해서 클래스 문제만 주구장창 푼 감이 없잖아 있어서 ㅎㅎ

 

아무튼, 이제부터 진짜 시작이다. 계속 정진하는 개발자가 되자.