쌉쌀한 무화과의 개발로그

[문제]

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

[문제 설명]

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

​

[제한사항]

numbers는 길이 1 이상 7 이하인 문자열입니다.

numbers는 0~9까지 숫자만으로 이루어져 있습니다.

"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

​

[입출력 예]

* 입출력 예 설명

예제 #1

[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2

[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

11과 011은 같은 숫자로 취급합니다.

>문제 풀이

찾은 소수를 중복없이 저장 및 카운트 하기 위해 자료구조로 hash set을 사용했습니다.

주어진 String numbers를 조합해서 만드는 건데, 주의점은 카드의 중복 사용이 안됩니다.

즉 사용했던 카드를 다시 사용할 수 없습니다. 그래서 boolean visited[]를 이용해서 이미 사용한 카드는 사용하지 못하도록 처리해주었습니다.

​

1) 완전탐색으로 만들 수 있는 숫자 조합 찾기

2) 숫자 조합이 0, 1이 아니면서 소수인지 판별한 후 true면 set에 저장

​

answer= set.size();

>전체 코드

import java.util.HashSet;
class Solution {
    static HashSet<Integer> set= new HashSet<>();
    static char[] arr;
    static boolean[] visited;
    
    public int solution(String numbers) {
        int answer = 0;
        arr= new char[numbers.length()];
        visited= new boolean[numbers.length()];
        
        for(int i=0; i<numbers.length(); i++){
            arr[i]=numbers.charAt(i);
        }
        recursion("", 0);
        
        answer= set.size();
        return answer;
    }
    
    //재귀: 가능한 숫자 조합을 찾고 소수여부에 따라 set에 추가
    public void recursion(String str, int idx){
        int num;
        if(str!="") {
            num= Integer.parseInt(str);
            if(isPrime(num)) set.add(num);
        }
        
        if(idx== arr.length) return;
        
        for(int i=0; i<arr.length; i++){
            if(visited[i]) continue;
            visited[i]= true;
            recursion(str+arr[i], idx+1);
            visited[i]= false;
        }
    }//rec
    
    public boolean isPrime(int num){ //소수 판별
        if(num==1||num==0) return false;
        for(int i=2; i<=Math.sqrt(num); i++){
            if(num%i==0) return false;
        }
        
        return true;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42839