분할 정복을 이용한 거듭제곱

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

 

문제 발생

• 위 문제를 풀며 문제가 쉬운데 왜 정답률이 20퍼 대인지? 라고 생각했다.
• 단순 반복문으로 계산하면 시간 복잡도는 O(n)이다.
• 하지만 시간 제한이 0.5초이고 n의 범위는 약 20억이기때문에 해당 방법을 사용하면 무조건 시간 초과가 뜰 수 밖에 없다!
• 다른 방법이 필요하다! 분할 정복을 이용하자

문제 해결 방안

• 3¹⁰⁰ = 3⁵⁰ * 3⁵⁰
• 위에처럼 분할을 하면 원래는 99번의 계산이 필요하겠지만 50번의 계산만이 필요하다.
• 3¹⁰⁰ = 3²⁵ * 3²⁵ * 3²⁵ * 3²⁵
• 한번 더 분할을 진행하면 99회에서 27회로 감소한다.
• 이런 식으로 분할을 하여 연산 횟수를 줄여보자!

• 이런 식으로 홀수 일때 처리 짝수 일때 처리 0 일때 처리 3가지로 구분해서 계산하면 된다!
• 또한 값이 진행하다 보면 무조건 long을 넘을 수 밖에 없기 때문에 모듈러의 성질을 이용하자
• 모듈러 성질
  • (a * b) % c = (a % c * b% c) %c 
  • 해당 성질을 이용하면 해결 가능하다!

 

결과

• 기존 코드는 O(n) 이었지만 분할 정복을 이용한 코드는 O(logn) 이 되었다.
• 이러한 방법은 거듭제곱 뿐만 아니라 행렬의 곱셈에서도 사용 가능하다!
• 상당히 먼 길을 돌아왔다.
• 기본적인 수학 상식인 지수 법칙과 모듈러 성질을 잘 기억해두고 써먹어보자!

 

https://seaking110.tistory.com/55