[C/C++] 코드업(codeup) 2640번 n의 k승 구하기 2

▽문제 바로가기

https://codeup.kr/problem.php?id=2640

n의 k승 구하기 2

---

입력

공백을 기준으로 int 범위의 정수 n과 k가 주어진다. (1<=n<=100,000, 1<=k<=100,000,000)

 

출력

n^k의 결과를 출력한다.

 

문제 풀이

 

일단 for문 돌려봤습니다.

 

#include <stdio.h>
#include <algorithm>

using namespace std;

int main(){
	
	int n, k;
	scanf("%d%d", &n, &k);
	
	long long int ret = 1;
	for(int i=0;i<k;i++){
		ret = (ret * n)%1000000007;
	}
	printf("%lld", ret);
	
	return 0;
}

 

1억을 반복하니 시간 초과가 발생한다

 

혹시나 했는데 역시나... 시간 초과

반복을 반으로 줄여봤으나 역시 실패...

결국 분할하여 풀기로 했습니다.

 

k는 최대 1억의 값을 가집니다. 2의 30승이 약 10억의 값을 가지니 1억의 반복도 결국 30번의 나누기 안에 해결됩니다.

 

계산 과정은 이진수로 설명 가능합니다. 예를 들어

 

2^11은 이진수로 1011입니다. 2^11 = 2^8 + 2^2 + 2^1 공식이 성립합니다. (11 = 8 + 2 + 1)

2^10은 이진수로 1010입니다. 2^10 = 2^8 + 2^2 공식이 성립합니다. (10 = 8 + 2)

 

즉, 나누었을 때 나머지가 1이면 계산을 진행하면 됩니다.

 

#include <stdio.h>

int main(){
	
	long long int n, k;
	scanf("%lld%lld", &n, &k);
	
	long long int arr[31] = {0};	//30회 안에 해결
	long long int ret = 1;
	
	arr[0] = n;
	arr[1] = (n * n)%1000000007L;
	//2의 30승까지 미리 저장해두기
	for(int i=2;i<30;i++){
		arr[i] = (arr[i-1] * arr[i-1])%1000000007L;
	}
	
	int count = 0;
	//계산과정(이진수만들기)
	while(k!=0){
		//나누었을 때 나머지가 1이라면 미리 저장한 값 계산
		if(k%2==1){
			ret = (ret * arr[count])%1000000007L;
		}
		count++;
		k = k/2;
	}
	//출력
	printf("%lld", ret);
	
	return 0;
}