1676 - 팩토리얼 0의 개수

• 난이도: 실버 5
• 날짜: 2023년 2월 27일
• 상태: Correct
• 추가 검토 여부: No
• 알고리즘 : DP

solution

• 이전 단계의 값에 특정 조건에 따라 추가 연산을 하면 되는 전형적인 DP문제이다.
• 5를 소인수로 몇 개를 가지고 있는지에 따라 0의 개수가 늘어나는 것이 핵심이다. (2는 2칸마다 1개씩 생성(?)되므로 충분하다.)
• 펙토리얼 연산이므로 현재의 수가 소인수로 가지는 5의 개수는 이전 단계의 값에 현 단계의 수에 대한 연산을 조건문을 통해 처리하면 된다.

code

#include <iostream>
using namespace std;

int main()
{
    int N;
    cin >> N;
    int arr[501] = {0, };
    for(int i = 1; i < 501; i ++)
    {
        arr[i] = arr[i-1];
        if(i%125 == 0) arr[i] += 3;
        else if(i%25 == 0) arr[i] += 2;
        else if(i%5 == 0) arr[i] += 1;
    }

    cout << arr[N] << endl;
    return 0;
}

ref

1676번: 팩토리얼 0의 개수