코드업(codeup) 2640 : n의 k승 구하기 2 C언어

▶문제 : n의 k승 구하기 2 (codeup.kr)

n의 k승 구하기 2

 

▶코드 작성(밑에 개선 코드 있음)

#include <stdio.h>

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);

    int cnt = 0, start = 1;//전체 제곱 횟수(cnt), 현재 제곱하고있는 횟수(start)
    long long num = 1, temp = n;//전체 제곱한 값(num), 현재 제곱하고있는 값(temp)
    
    while (cnt < k)//전체 제곱 횟수가 k와 같거나 크면 종료
    {
        if (start * 2 + cnt <= k)//현재 제곱하고있는 횟수*2와 전체 횟수가 k를 넘지 않을 때
        {
            start += start;//제곱 횟수
            temp = (temp * temp) % 1000000007;//제곱
        }
        else//현재 횟수*2 + 전체 횟수가 k를 넘으면
        {
            cnt += start;//넘기 전 횟수를 cnt에 저장
            start = 1;//다시 1부터 시작
            num = (num * temp) % 1000000007;//넘기 전 제곱한 값을 num에 저장
            temp = n;//다시 n부터 시작
        }
    }

    printf("%lld", num);

    return 0;
}

start와 temp변수로 미리 제곱을 해서 값을 넘으면 그 전 값을 저장하고 다시 처음부터 제곱하는 방식으로 풀고 나서 다른 풀이가 있는지 살펴보았는데 분할 정복 알고리즘으로 쉽게 풀 수 있어서 다시 코드를 작성해보았다.

 

 위 코드가 n값을 제곱하고 또 제곱한 값을 제곱하여 빠르게 찾아내는 방식이라면 분할 정복을 이용한 것은 k값을 2로 나누면서 빠르게 찾아내는 방식이었다.

 

▶개선 코드(분할 정복)

#include <stdio.h>

long long func(int n, int k)
{
    long long num, temp;
    if (k > 1)//k값이 1보다 크다면
    {
        temp = func(n, k / 2);//k를 2로 나누어 다시 func함수 호출
        num = (temp * temp) % 1000000007;//temp값에서 구한 값을 제곱해준다
        if (k % 2 == 1) num *= n % 1000000007;//k가 홀수라면 n을 곱해준다
    }
    else num = n;//k가 1이면 num=n
    return num % 1000000007;
}

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    printf("%lld", func(n, k));

    return 0;
}

 

▶해석

분할 정복을 이용하여 n^k = ( n^(k/2) )^2 공식으로 풀 수 있다. 예를 들어

2^4 = ( 2^2 )^2 = ( ( 2^1 )^2 )^2

= ( 2 x 2 )^2 = 2 x 2 x 2 x 2

이런 식으로 풀어지는 것이다.

 

하지만 k값이 짝수일 때는 위처럼 쉽게 풀어지지만 홀수라면 살짝 추가 부분이 있다.

n^k = ( n^(k/2) )^2 x n 뒤에 n만 한번 곱해주면 된다.

2^5 = { ( 2^2 )^2 } x 2 = { ( ( 2^1 )^2 )^2 } x 2

= { ( 2 x 2 )^2 } x 2 = { 2 x 2 x 2 x 2 } x 2 = 2 x 2 x 2 x 2 x 2

이런 식으로 이 문제도 해결하면 된다.