B2004

개요

백준 문제 2004번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 1시간 30분
https://www.acmicpc.net/problem/2004

문제

nCm의 끝자리 의 개수를 출력하는 프로그램을 작성하시오.

코드

#include <iostream>
using namespace std;

long long getCountFromFact(long long n)
{
	long long five = 0;
	for(long long i=5;i<=n;i*=5)
	{
		five += n/i;
	}
	return five;
}

long long getCountFromFactTwo(long long n)
{
	long long two = 0;
	for(long long i=2;i<=n;i*=2)
	{
		two += n/i;
	}
	return two;
}


int getCountFromNum(string str)
{
	int count = 0;
	for(int i=str.size()-1;i>=0;i--)
	{
		if(str[i] != '0')
		{
			return count;
		}
		count++;
	}
}


void solve()
{
	long long n,c;
	cin >> n >> c;
	c = min(n-c,c);
	long long upper,mid;
	long long upperTwo,midTwo;
	if(c == 0)
	{
		cout << 0;
	}
	else if(c == 1)
	{
		cout << getCountFromNum(to_string(n));
	}
	else
	{
		upper = getCountFromFact(n);
		mid = getCountFromFact(n-c) + getCountFromFact(c);
		upperTwo = getCountFromFactTwo(n);
		midTwo = getCountFromFactTwo(n-c) + getCountFromFactTwo(c);

		cout << min((upper - mid),(upperTwo-midTwo));
	}
	
}


int main()
{
	solve(); 
}

풀이

이전에 배웠던 팩토리얼을 직접 계산하지않고 0을 추출하는 것을 이용한 문제이다.
(2와 5의 쌍의 갯수를 계산하여 푸는 방법)
팩토리얼 0의 갯수 구하기 문제에서는 2가 의미가 없었다 (항상 5의 개수가 적어서)
하지만 이번 문제도 동일하게 생각해서 풀었는데, 나눠지는 팩토리얼에서 2를 나누면
나누는 팩토리얼에 영향을 주게되므로 2의 개수도 고려해야 했다.

배울 점, 메모

오늘로 6문제를 풀어보았는데,
스스로 완벽하게 푼 문제는 기초문제들 뿐이었다.
하지만 어떡하겠는가?
완벽하게 안다면 배울 필요가 없지 않는가