[C#] 백준 1676번 문제풀이

안녕하세요.

백준 1676번 '팩토리얼 0의 개수' 문제 풀이를 진행하도록 하겠습니다.

해당문제는 주어진 수 N의 팩토리얼 뒤에서부터 0이 아닌 숫자가 나올때까지 0이 몇개 존재하는지 찾아내는 문제입니다.

 

이 문제를 처음엔 실제 팩토리얼을 구하고 답을 구하는 문제인줄 알았으나 그렇게 간단한 문제가 아니었습니다. 

N은 500까지 입력으로 들어올 수 있고, 이걸 팩토리얼로 구하면 그 수는 상상을 초월할정도로 많아집니다 😵

그래서 0이 만들어지기 위한 조건은 2와 5가 한 쌍이 되어야 한다는 점에서 힌트를 얻었습니다. 예를들어, 10은 2x5로 만들어지는 것 처럼 말입니다. 그런데, 2는 항상 5보다 많음으로 N 팩토리얼에서 얼마나 많은 5가 있느냐를 구하는게 문제의 핵심입니다.

이제 문제를 풀어보겠습니다.

 

입력예제

10

 

출력예제

2

 

먼저, 입력으로 N을 받아옵니다. 그리고 형식을 int로 변환해줍니다.

다음줄에는 0의 개수를 저장할 count 변수를 만들어줍니다.

int N = int.Parse(Console.ReadLine());
int count = 0;

 

이제 문제의 핵심이 되는 줄 입니다.

while문을 사용하여 N이 5 이상일동안 반복하도록 해줍니다.

반복문 안에서 N / 5의 값을 count에 더해주고 N을 5로 나눠줍니다.
마지막으로 카운트를 출력하면, 정답입니다.

while (N >= 5)
{
    count += N / 5;
    N /= 5;
}
Console.WriteLine(count);

 

팩토리얼은 비교적 간단한 문제임에도 불구하고 문제를 푸는동안 계속 막막했었습니다.

이번 문제를 통해 수학문제의 필요성을 다시 한번 느끼는 계기가 되었던 것 같습니다 😶‍🌫️
다음은 전체코드입니다.

 

전체코드

using System;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int count = 0;

        while (N >= 5)
        {
            count += N / 5;
            N /= 5;
        }

        Console.WriteLine(count);
    }
}