과제 도전기 - 2

x의 n제곱을 구하는 과제이다

math.h 라이브러리의 pow를 사용하면 쉽게 해결 할 수 있지만 분할정복을 활용해서 과제를 해결했다

#include <stdio.h>

void print(int *x, int *n){
    printf("x를 입력하세요 : ");
    scanf("%d",x);
    printf("n을 입력하세요 : ");
    scanf("%d",n);
}

int power(int x, int n){
    if(n==1){
        return x;
    }

    int tmp = power(x,n/2);

    if(n%2==1){
        return tmp*tmp*x;
    }
    return tmp*tmp;
}

int main(void){
  int x,n;  

  print(&x,&n);

  printf("%d의 %d 제곱은 %d입니다.",x,n,power(x,n));
}

print함수는 x ,n의 값을 입력받는 함수이다

power함수가 제곱을 구하는 함수인데 분할정복을 통해 n이 홀수일 때, x를 곱한 뒤 x^(n/2), x^(n/2)로 나누면서 진행한다

O(logN)이기 때문에 빠르게 해결 할 수 있다