백준 1676번 : 팩토리얼 0의 개수

문제 접근

---

1. Factorial 계산 과정에서 필요 없는 것들은 날리자.
   
     N이 500이면 오버플로우가 생길 것 같아서 계산 과정에서 날릴 수 있는 것들은 날리기로 했다.
   
     이에 뒷자리가 0인 경우, 어떤 수와 곱해도 0은 유지된다는 특성으로부터 계산 과정의 뒷자리에 0이 올 때마다 자릿수를 내리고, 답에 1을 추가하는 방식으로 구현했다.
   
   문제 : 500이면 0을 제외해도 자릿수 자체가 크기 때문에 여전히 오버플로우가 발생한다.
   
   
2. 10을 만드는 수를 필터링해서 아예 곱셈을 하지 않아도 되게 나머지를 다 날리자.
   
     중학교 때쯤 배웠던 지수 곱셈이 생각났다. 1부터 N까지의 어떤 수든 분해하면 $x^{a}\times y^{b}\times z^{c}$ 와 같은 형태로 표현된다.
   
     이때 10을 만드는 수는 2와 5이므로, 1부터 N까지 수를 분해하면서 2와 5의 지수를 구하고 그중 최소 값이 10의 자릿수이므로 이를 답으로 출력하도록 수정했다.

 

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

1676번: 팩토리얼 0의 개수

 

 

 

문제 코드

---

#include <iostream>

using namespace std;

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, check, numOf2, numOf5;

    numOf2 = numOf5 = 0;

    cin >> N;

    while (N)
    {
        check = N--;

        while (check % 5 == 0)
        {
            ++numOf5;
            check /= 5;
        }

        while (check % 2 == 0)
        {
            ++numOf2;
            check /= 2;
        }
    }

    cout << ((numOf5 < numOf2) ? numOf5 : numOf2);
}

 

 

 

느낀 점

---

    풀이에 대한 느낀 점을 언급하기 전에 오랜만에 알고리즘을 풀이한 이유를 적으려고 한다.

 

    요즘 단순 디자인 뿐만 아니라 아트(Techical Art)까지 발을 넓히면서 이것저것 하고 있다. 한 번에 여러 가지를 하다 보니 어떤 날은 특정 파트에 대해 아무것도 못할 때가 있는데, 나는 이럴 때일수록 조금씩이라도 무언가를 꾸준히 해야 된다고 생각했다.

 

    이에 프로그래밍은 알고리즘, 디자인은 칼럼 리뷰, 아트는 유튜브를 보면서 계속 감각을 유지하기로 했다. 매일 모든 것에 대한 글을 작성하지는 못하겠지만 그래도 할 수 있는 것들은 조금씩 해보려고 한다.

 

 

    솔직히 전투 디자이너라는 디자이너 파트로 나아가려고 하는 이상 알고리즘이 거의 무용하다는 것은 잘 알고 있다. 이건 프로그래머로 미련이 남아서도, 취업을 준비하기 위해서도 아닌 그저 problem solving, 그러니까 문제 해결 역량을 다듬기 위해 하는 활동이다.

 

    문제 해결 역량은 단순히 프로그래밍 뿐만 아니라 디자인 과정을 넘어 삶의 전반에 적용되는 기술이기에 연구에 도움이 될 겸 조금 더 논리적으로, 그리고 효과적으로 사고하는 방법을 벼리고자 이렇게 알고리즘 풀이를 하려고 한다.

 

 

    알고리즘을 풀이한 이유는 이쯤하고 간단하게 어제 풀이한 문제의 느낀 점을 적도록 하겠다.

 

 

1. 필수적인 역할과 필요 없는 역할을 구분하자.
   
     이번 문제의 목표인 '0의 개수'를 역할로 변환하면 '10의 지수 승을 구하는 것'이다. Factorial이라는 함정에 빠져 'factorial의 결과를 구하는 것'이라는 역할까지 떠안지 말자.
   
     목표를 역할로 정리하고, 역할을 위해 어떤 정보를 저장하고 활용해야 하는지 고민해 보도록 하자.