백준 1676 팩토리얼 0의 개수 c++ [컴공과고씨]

https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

이 문제는 처음에 고민을 하다가 팩토리얼 숫자를 그리면서 규칙을 좀 살펴보니 5배수가 곱해질때마다 뒤에 0 이 붙는 것을 보고 이것을 이용해 풀었다. 왜냐하면 10이 곱해지려면 2와 5가 필요한데 2는 항상 5보다 많기 때문에 5가 몇개 있는지 세주면 된다. 

주의 해야할 것은 5의 배수중 25 와 같이 5가 2번 곱해진것은 0이 2개가 추가 됨에 주의 해주면된다.

위 방법과 다이나믹 프로그래밍을 이용하여 하나씩 0의 개수를 저장하는데 5배수가 들어있는 수가 곱해지는 차례에는 

i-5번째에 있는 수에 5의 개수를 더해주면된다. 5의 배수가 들어가 있지 않다면 i-1번째의 0의 개수와 같다.

 

단계별 풀이

1. dp 배열 초기화 및 선언

2. i=5부터 시작해서 n까지 가는데 i를 5로 나누었을 때 나머지가 0이라면 5가 있는 것이므로 5가 몇번 곱해지는 셈

3. dp[i] 에 dp[i-5] + 아까 센 5의 개수 

4. 만약 5로 나누었을 때 나머지가 0이 아니라면 5가 없는것이므로 0의 개수 유지

 

전체 코드

#include <iostream>
using namespace std;
int main(){
    int dp[502];
    int n;
    cin >> n;
 
    dp[0] = 0;
    dp[1] = 0;
    dp[2] = 0;
    dp[3] = 0;
    dp[4] = 0;
    int cnt;
    int x;
    for (int i = 5; i <= n;i++){
        if(i%5==0){ // 5가 곱해진 수라면
            x = i;
            cnt = 0;
            while(x%5 == 0){ // 5의 개수 세기
                x /= 5;
                cnt++;
            }
            dp[i] = dp[i - 5] + cnt; 
        }else{
            dp[i] = dp[i - 1]; // 5가 없는 것이 곱해진 경우
        }
    }
 
    cout << dp[n];
    return 0;
} //31 min

체감난이도	걸린시간	참고	사용 알고리즘, 문법
중하	31min	x	다이나믹 프로그래밍(dynamic programming)