[SWEA 1217] 거듭 제곱 C++

 

SW Expert Academy

 

 

문제풀이

 

N의 M 거듭제곱 값을 구하는 프로그램을 재귀호출을 이용하여 구현하는 문제다.

 

M이 0일 때는 1, 그 이외의 경우에는 n * power(n, m - 1)을 리턴해주면 거듭제곱을 쉽게 구할 수 있다.

 

 

하지만 이 방법은 시간 복잡도가 O(N)이라서 지수가 커지면 문제가 발생할 수 있다.

이때 분할정복을 이용하면 O(logN)의 시간 복잡도로 거듭 제곱을 구할 수 있다.

 

 

2의 8제곱을 예로 들어보자.

 

 

2의 8제곱은 2를 8번 곱하여 구할 수도 있지만 거듭 제곱을 3번만 해서 해결할 수도 있다.

홀수번 거듭 제곱을 하는 경우에는 N을 한 번 곱하고 N의 (M-1)/2제곱을 제곱하는 것으로 해결할 수 있다.

 

 

• n이 1이면 return C
• n이 2 이상일 때 n이 짝수면 지수를 반으로 나눠 거듭 제곱을 구한다
• n이 2 이상일 때 n이 홀수면 (n - 1)지수를 반으로 나눠 거듭 제곱을 구하고 C를 곱해준다 

 

 

C++ 코드