코드업 2640

코드업 2640번을 풀어보겠습니다.

어떤 정수 n과 k가 입력되면, n^k의 값을 1,000,000,007로 나눈 나머지를 출력하시오.

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

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

1. 문제 분석

문제는 굉장히 간단합니다. n, k 값을 입력받아 n^k 만 구하면 되지만 그 값이 크다는 것을 해결해야 합니다.

 

2. 순서도

 

3. 코드

#include <stdio.h>

long long int n, k;
long long int a[100000000];

int f(long long int n, long long int k){
	if(k==1) return a[k]=n%1000000007;
	f(n,k-1);
	if(k>1) return a[k]=a[k-1]*n%1000000007;
}

int main(){
	scanf("%lld %lld", &n, &k);
	printf("%lld", f(n, k));
}

처음에는 시간을 제대로 고려하지 않고 재귀함수를 통해 위의 코드처럼 짰다가 실행이 되지 않았습니다.

시간을 줄이기 위해서 다른 방법을 찾아보았습니다.

n^k/2를 구해서 그 값을 제곱하고 k가 홀수일 때는 n을 한번 더 곱해주는 방법으로 해결해보았습니다.

계산할 때마다 매번 나머지를 구하여 수가 많이 커지지 않도록 해주었습니다.

 

#include <stdio.h>

int n, k;
long long int t;

long long int f(int k){
	if(k==1) return n;
	else{
		t=f(k/2)%1000000007;
		t=(t*t)%1000000007;
		if(k%2==1){
			t=(t*n)%1000000007;
		}
	}
	return t;
}

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

 

큰 수를 연산하기 위한 메모이제이션에 대해 더 익숙해져야 할 것 같습니다.