백준 알고리즘 1009번 문제 풀이 (자바)

백준 알고리즘 1009번 문제입니다.

 

간단하게 생각해보면 A에 B제곱을 구하여 뒷자리만 가져오면 됩니다.

이때, 뒷자리가 0이면 10으로 바꿔주면 됩니다.

그리고 숫자를 표한할 수 있는 자리수가 정해져 있기 때문에 제곱을 구할때 마다 10으로 나눈 나머지만 가지고 계산을 합니다.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int T = s.nextInt();
		int a,b,r;
		for(int j=0;j<T;j++) {
			a=s.nextInt();
			b=s.nextInt();
			r=1;
			
			for (int i=0;i<b;i++) r=(r*a)%10;
			if(r==0) r=10;
			System.out.println(r);
		}
		s.close();
	}
}

 

이렇게 풀게 되면 메모리와 시간은 아래와 같습니다.

여기에 소스를 조금만 더 추가해 준다면 시간은 훨씬 줄어들게 됩니다.

우선, 1~10까지의 숫자들의 제곱을 보면,

1,5,6,10의 제곱의 뒷자리는 항상 같고,

4와 9는 짝수제곱과 홀수제곱의 뒷자리가 같습니다.

나머지 2,3,7,8은 1제곱과 5제곱, 2제곱과 6제곱의 마지막자릿수가 같은걸 알 수 있습니다.

이것을 이용하여 소스를 조금 수정하면 다음과 같습니다.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int T = s.nextInt();
		for(int j=0;j<T;j++) {
			int a=s.nextInt();
			int b=s.nextInt();
			int c=0;
			int answer=1;
			
			if(a%10 == 0 || a%10 == 1 || a%10 == 5 || a%10 == 6) {
				answer=a%10;
			}else if(a%10 == 4 || a%10 == 9) {
				c = b%2;
				if (c==0) c=2;
			}else {
				c = b%4;
				if (c==0) c=4;
			}
			
			for (int i=0;i<c;i++) answer=(answer*a)%10;
			if (answer==0) answer = 10;
			System.out.println(answer);
		}
		s.close();
	}
}

a가 0,1,5,6 일경우 a의 값을 바로 집어넣고, 나머지 숫자는 2또는 4로 나눈 나머지를 구하여 for문으로 뒷자리를 구합니다.

답이 0일경우 10으로 교체를 해주고 출력을 해주면 끝입니다!

채점을 해보면 시간이 훨씬 줄어든 것을 볼 수 있습니다!!!