[알고리즘] 백준 - 10872번 : 팩토리얼 / 1676번 : 팩토리얼 0의 개수 / 2004번 : 조합 0의 개수 / 11653번 : 소인수분해

알고리즘 문제 출처 : https://www.acmicpc.net/problem/10872

10872번: 팩토리얼

 

내가 작성한 코드

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long factorial = 1;
		int n = sc.nextInt();
		for(int i=2; i<=n; i++) {
			factorial *= i;
		}
		System.out.println(factorial);
	}
}

 

 

---

알고리즘 문제 출처 : https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 

내가 작성한 코드

n!의 10의 거듭제곱이 얼마나 되는지 알아보면 된다. 그러려면 n을 소인수분해하여 2의 거듭제곱과 5의 거듭제곱이 몇 개인지 각각 알아보면 되고, 둘 중 작은 수가 정답이 된다. 그런데 소인수분해를 하면 항상 5가 2보다 더 적게 나오므로 5의 거듭제곱이 총 몇 개인지 알아보면 된다. 

단순하게 생각하면 n에서 5의 배수가 몇 개인지 구하면 된다. 하지만 25, 50, 75, ... 같이 (5의 배수이면서) 25의 배수는 5가 두번 곱해져있다. 또 125, 250, 375, ... 같이 (5의 배수이자 25의 배수이면서) 125의 배수는 5가 세번 곱해져있다. (...이하 생략...)

그러므로 n에서 5의 배수가 몇 개인지 먼저 구하고, n에서 25의 배수가 몇 개인지 구해서 더하고, n에서 125의 배수가 몇 개인지 구해서 더하고, (...이하 생략...) 이렇게 구하면 누락되는 5가 없게 된다. 

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int answer = 0;
		for(int i=5; i<=n; i*=5) {// i=5,25,125,...
			answer += n/i;
		}
		System.out.println(answer);
	}
}

 

 

---

알고리즘 문제 출처 : https://www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

 

내가 작성한 코드

23C14 = 23!/(14!*9!)과 같다. 따라서 분자와 분모의 소인수분해를 따로 해줘서 분자의 2와 5의 개수에서 분모의 2와 5의 개수를 빼줘야 한다.(약분의 과정이 있으므로 소인수분해시 5의 개수만 구하면 안 되고 2의 개수도 함께 구해줘야 한다.)  

수 범위가 크므로 int형으로 풀면 런타임 에러가 난다. 자료형을 꼭 long형으로 선언할 것.

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long m = sc.nextLong();
		long two = count(n)[0] - Math.abs(count(m)[0]+count(n-m)[0]);
		long five = count(n)[1] - Math.abs(count(m)[1]+count(n-m)[1]);
		System.out.println(Math.min(two, five));
		
	}
	
	public static long[] count(long a) {
		long[] temp = new long[2];
		for(long i=2; i<=a; i*=2) {
			temp[0] += a/i;
		}
		for(long i=5; i<=a; i*=5) {
			temp[1] += a/i;
		}
		return temp;
	}
}

 

 

---

알고리즘 문제 출처 : https://www.acmicpc.net/problem/11653

11653번: 소인수분해

 

내가 작성한 코드

1은 소수가 아니므로 1을 입력했을 때 출력되면 안 된다.

import java.util.Scanner;

public class Main {
	
    public static void main(String args[]) {
    	Scanner sc = new Scanner(System.in);
    	long n = sc.nextLong();
    	long temp = n;
    	for(int i=2; i<=n; i++) {
    		while(temp%i==0) {
    			System.out.println(i);
    			temp/=i;
    		}
    	}
    }
}