쌉쌀한 무화과의 개발로그

[문제]

N!의 값을 계산한 후에, 0이 아닌 가장 낮은 자리 수를 구하시오.

예를 들어, 4! = 24 이기 때문에, 0이 아닌 가장 낮은 자리 수는 4이다. 또, 5! = 120이기 때문에, 0이 아닌 가장 낮은 자리 수는 2 이다.

​

[입력]

첫째 줄에 N이 주어진다. N은 20,000보다 작거나 같은 자연수 이다.

​

[출력]

첫째 줄에 N!의 0이 아닌 마지막 자리수를 출력한다.

​

[예제]

>문제 풀이

예전에 틀렸던 문제를 다시 풀어보았습니다.

실버라더니 어려웠던 문제...

​

가끔 참고하는 블로그인데, 이번에도 도움을 받았습니다.

설명을 정말 잘 해놓으셨어요..bb

참고한 블로그 링크: https://steady-coding.tistory.com/322

위의 블로그에 너무 잘 정리되어있기 때문에 이번 포스팅은 제가 이해한 내용과 흐름을 위주로 추후에 다시 보기 위해 작성하겠습니다.

​

먼저 이 문제는 N!에 대해 0을 제외한 마지막 자릿수를 구하는 문제입니다.

입력되는 N의 범위가 무려 20,000 까지기 때문에 무작정 for문을 돌리면 시간초과가 일어납니다.

그래서 이 문제는 dp로 풀게 되었는데, 아래의 로직을 읽어보다 보면 왜 dp로 풀었는지 이해가 될 것입니다.

​

그래서 factorial의 계산에 대해 생각해 볼 필요가 있는데요.

먼저 끝자리에 0이 생기는 조건에 대해 생각해보면, 10의 제곱수를 곱하게 될 경우 끝자리에 0이 붙게 됩니다. 즉 2와 5의 조합에 따라 0이 생긴다고 보면되죠.

​

15!

= (1 x 2 x 3 x 4 x 5) x (6 x 7 x 8 x 9 x 10) x (11 x 12 x 13 x 14 x 15)

5의 배수를 앞으로 모아줍니다.

= (5 x 10 x 15) x (1 x 2 x 3 x 4) x (6 x 7 x 8 x 9) x (11 x 12 x 13 x 14)

​

뒤에 형광펜으로 색칠된 부분의 digit은 모두 4인것을 알 수 있습니다.

왜냐면 끝자리 기준으로

1 x 3 = 3, 2 x 4 = 8 >> digit= 4

7 x 9 =63, 6 x 8 =48 >> digit= 4

따라서 끝자리가 1, 2, 3, 4인 묶음이든, 6, 7, 8, 9인 묶음이든 0이 아닌 마지막 수는 4가 나옵니다.

​

= (5 x 10 x 15) x (1 x 2 x 3 x 4) x (6 x 7 x 8 x 9) x (11 x 12 x 13 x 14)

= 5^3 x 6 x 2^2 x 2^2 x 2^2

이제 0을 만들어내는 10을 없애주기 위해 2와 5를 조합해줍니다.

= 10^3 x 6 x 2^3 //10은 앞서 말했듯 끝자리 수에 영향 없는 0만 만들어주기 때문에

= 6 x 2^3

= 3! x 2^3

​

∴ N에 대해서 위의 방식대로 정리하게 되면

= A! x 2^p 의 구조가 나오게 됩니다.

우리는 이제 이 구조로 끝자리를 구할 수 있습니다.

​

이제 dp를 어떻게 적용시킬지 알아봅시다.

위의 식을 좀 더 정리해볼건데요.

각 숫자의 끝자리를 dp[] 배열에 담는다고 했을 때, 3!의 끝자리는 dp[3]에 담겨있겠죠?

그리고 2의 제곱수 같은 경우에는 끝자리가 2^1=2, 2^2=4, 2^3= 8, 2^4=6 이 반복됩니다.

즉, (dp[3] x 8)%10 이 15!의 0이 아닌 마지막 자릿수 입니다.

​

그렇다면 17!은 어떻게 구할 수 있을까요?

17!= dp[15] x 16 x 17

= dp[15] x 6 x 7

​

즉, N보다 작은 5의 배수의(=temp) dp값을 기준으로 temp+1~ N까지의 수를 곱해주면서 %10을 해주면 구할 수 있습니다.

​

​

* 팩토리얼 계산해주는 사이트 링크 입니다. 참고하세요~

https://ko.numberempire.com/factorialcalculator.php

>전체 코드

import java.util.Scanner;

public class Main {
	
	public static void main(String [] args) {
		int N, temp, dp[];
		
		Scanner scan= new Scanner(System.in);
		
		N= scan.nextInt();
		dp= new int[N+1];
		
		//2^n digit: 2 4 6 8
		dp[1]= 1;
		dp[2]= 2;
		dp[3]= 6;
		dp[4]= 4;
		
		for(int i=5; i<=N; i++) {
			if(i%5==0) {
				temp= i/5;
				dp[i]= (dp[temp]*(int)Math.pow(2, temp%4))%10;
			}else{
				temp= (i/5)*5;
				dp[i]=dp[temp];
				for(int j=temp+1; j<=i; j++) {
					dp[i]=dp[i]*j%10;
				}
			}
		}//end for
		
		System.out.println(dp[N]);
	}	
}

https://www.acmicpc.net/problem/2553