본문 바로가기
[C++] 알고리즘 교육/5. 기본정렬

[알고리즘 5.3.7] 기본정렬 - combinationzero

by 안산학생 2019. 4. 25.

문제


n명의 사람중 m명을 순서에 상관없이 뽑는 경우의 수를 조합이라고 하며 nCm으로 나타낸다.

nCm은 수식으로 n!/m!(n-m)! 으로 구할 수 있다. (5! = 1 * 2 * 3 * 4 * 5)

n과 m이 주어졌을때 nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.  

입력


첫째 줄에 정수 n, m(0≤m≤n≤1,000,000)이 들어온다.

 

출력


첫째 줄에 0의 개수를 출력한다.

 

예제 입력

25 12

예제 출력

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//0의 조합
//2차원 배열은 이렇게 크기가 크면 런타임 에러,
 
#include <stdio.h>
 
int main() {
  
  int num1;
  scanf("%d",&num1);
  int temp = num1;
  int su1 = num1;
  
  //a = 2, b = 5;
  int a = 0, b = 0;
  int aa = 0, bb = 0;
 
  while(1){
    if(temp<1){
      break;
    }
    if(num1%5==0){
      num1 = num1/5;
      b++;
    }else if(num1%2==0){
      num1 = num1/2;
      a++;
    }else{
     if(temp == 2){
        break;
      }else{
        temp--;
        num1 = temp;
      }
    }
  }
  
  scanf("%d",&num1);
  temp = num1;
  int su2 = num1;
  while(1){
    if(temp<1){
      break;
    }
    if(num1%5==0){
      num1 = num1/5;
      bb++;
    }else if(num1%2==0){
      num1 = num1/2;
      aa++;
    }else{
     if(temp == 2){
        break;
      }else{
        temp--;
        num1 = temp;
      }
    }
  }
  
  num1 = su1-su2;
  temp = num1;
  while(1){
    if(temp<1){
      break;
    }
    if(num1%5==0){
      num1 = num1/5;
      bb++;
    }else if(num1%2==0){
      num1 = num1/2;
      aa++;
    }else{
     if(temp == 2){
        break;
      }else{
        temp--;
        num1 = temp;
      }
    }
  }
 
  int aaa=0,bbb=0;
  aaa = a - aa;
  bbb = b - bb;
  
  if(aaa>bbb){
    printf("%d",bbb);
  }else if(aaa<bbb){
    printf("%d",aaa);
  }else if(aaa==bbb){
    printf("%d",aaa);
  }else{
    printf("0");
  }
  
  return 0;
}

댓글