풀이
끝자리 0의 개수는 5와 2의 곱의 개수로 만들어진다. 하지만 2의 개수와 5의 개수만 세어주면된다.
5!은 1개 10!은 2개 15!은 3개 20!은 4개 25!은 6개다.
이런식으로 n!에 대해 5의 개수를 계산하는 메소드를 만들고
입력한 N, M에 대해 N! M! (N-M)!의 5의 개수를 구한다
N!의 5의 개수에서 나머지 둘을 빼주면 끝자리 0의 개수를 구할 수 있다.
반례 - N=5, M=4
2의 개수가 충분하다고 생각할 수 있지만 n=5 m=4가 입력된다면 각각의 5의 배수는 1개, 0개 이므로 1이라는 결과값을 낸다.
하지만 5! ÷ 4!은 5이며 10이 되지 않는다. 이는 둘에서 발견되는 2의 배수의 개수를 고려하지 않았기 때문이다.
위에서 만들어준 논리와 같은 2의 배수의 개수를 구해주는 메소드를 만든다.
결과
5의 배수의 개수와 2의 배수의 개수를 기준으로 각각 연산값을 구하고 더 작은 값을 결과로 출력한다.
5! 4!의 각각 2의 개수는 3개 3개므로 결과값은 3-3=0이 된다.
사용자가 5 4 를 입력하면 코드에서 5의 배수 개수 1과 2의 배수의 개수 0을 구하고 더 작은 값인 0을 출력한다.
import java.util.*;
public class Main {
static int Five(int N, int sum) {
if(N==0)return sum;
return Five(N/5,sum+N/5);
}
static int Two(int N, int sum) {
if(N<=1)return sum;
return Two(N/2,sum+N/2);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N=sc.nextInt(),M=sc.nextInt();
int five=Five(N,0)-Five(M,0)-Five(N-M,0);
int two=Two(N,0)-Two(M,0)-Two(N-M,0);
System.out.println(Math.min(five, two));
}}
'Study > Baekjoon' 카테고리의 다른 글
Baekjoon23795: 사장님 도박은 재미로 하셔야 합니다 (0) | 2021.12.08 |
---|---|
Baekjoon9375: 패션왕 신해빈 (0) | 2021.12.07 |
Baekjoon11051: 이항 계수2 (0) | 2021.12.05 |
Baekjoon11050: 이항계수 (0) | 2021.12.04 |
Baekjoon3036: 링 (0) | 2021.12.03 |