반응형
문제 출처 :
https://www.acmicpc.net/problem/1676
알고리즘 분석 :
간단하게 설명하고자 한다.
이 문제는 n!을 할 때 끝자리 0이 몇개 나오는지 묻는 문제이다.
잘 생각해보자.
2와 5가 곱해지면 10이 된다.
2 2 와 5 5 가 곱해지면 100이된다.
2 5 2 5 2 5가 곱해지면 1000이 된다.
따라서 우리는 2와 5의 개수를 n! 내에서 세면 된다.
그때의 2와 5의 개수 중 더 작은 값이 정답이 된다.
예를들어 2 2 2 5 5면 200이기에 0은 2개이고, 정답은 5가 2개이기에 답은 2이다.
자세히 생각해보면 어떤 수 n!에 대해 2와 5의 개수는 항상 5가 작음을 알 수 있다.
따라서 이 문제는 n!에서의 5의 개수를 세는 것과 같아진다.
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 | #include <iostream> #include <cstdio> #define min(a,b)(a < b ? a : b) using namespace std; int main() { int n, tmp; scanf("%d", &n); int two = 0, five = 0; for (int i = 1; i <= n; i++) { tmp = i; while (tmp) { if (tmp % 2 == 0) { two++; tmp /= 2; } else break; } tmp = i; while (tmp) { if (tmp % 5 == 0) { five++; tmp /= 5; } else break; } } printf("%d",min(two, five)); return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
따라서 이 문제는 n!에서의 5의 개수를 세는 것과 같아진다.
아래 내용은 몇년 전 내가 작성한 어리석은 알고리즘 해석 방법이다.
값이 500이상이 되어 10^8까지만 범위가 되도 아래 코드는 작동 할 수 없다.
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[1475번] 방 번호 (0) | 2016.07.22 |
---|---|
[2669번] 직사각형 네개의 합집합의 면적 구하기 (0) | 2016.07.21 |
[10164번] 격자상의 경로(Dynamic Programming, Mathematic) (0) | 2016.07.20 |
[11809번] 충돌 (0) | 2016.07.19 |
[5988번] 홀수일까 짝수일까 (0) | 2016.07.10 |