[Inflearn] N1 에서 0의 개수(소인수분해 응용)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 이건 너무 간단한걸?! 하지만 방심하면 시간초과가 뜨거나 막히거나 하겠지..

     일단 최대 N은 1,000 로 N^2 을 하더라도 1,000,000, 음~ 충분하군

    

     N = 5 일 경우, 

     5 x 4 x 3 x 2 x 1 을 먼저 계산해보자.

     단순하게 누적곱을 해주면 될 것 같은데.. 왜이렇게 뭔가 함정이 있을 것 같지

     결과는 120, 

     여기서 %10을 해주면서 0일 경우 cnt++ 를 해주면 될 것 같다.

     

     뭔가 찝찝한 마음으로 우선 코드로 옮겨보자..?

      역시나.. 예상은 적중했다. 

      충분하기 개뿔! 1000! 를 왜 생각을 안 해봤지ㅋㅋㅋ

      1000이 들어오면 int 는 커녕 long long 의 범위까지 넘어가버린다.

      결코 방심하다가 큰 코 다치는 것이다..

      안 풀릴 생각으로 약간의 가라(?)를 섞어서 풀어봤는데 신기하게 풀리긴 했다.

      사실 testcase가 적어서 풀린 것일 수도 있는데.. 맞는 것 같다..

      무튼 구간곱(?)을 이용하였는데,

      몇 가지 testcase로 시도해보니까 예를 들어

      N = 12일 경우,

      1 ~ 5 까지의 곱 = 120

      6 ~ 10 까지의 곱 = 520

      11 ~ 12 까지의 곱 = 132

      에서 각 구간곱의 일의 자리부터 연속적으로 0이 몇개 있는지 cnt++ 해주면 답이 나왔다.

      그걸 그냥 코드로 옮겨보았고, 보니까 십의자리가 5인 testcase는 wrong result 가 나와서

      마지막에 십의자리가 5인 경우 cnt -= 1 을 해주었고, 전체적으로 + 1이 더 나와서 출력 때 cnt - 1 을 해주었다..

      말 그대로 그냥 가라로 풀어버렸다.. 나중에 다시 풀어봐야지ㅠㅠ

#. Code

 1. 가라 코드..

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    //freopen("input.txt", "rt", stdin);
 
    int n, i, cnt = 0, p = 2;
    long long sum = 1;
 
    scanf("%d", &n);
 
    while (1)
    {
        sum = 1;
 
        for (i = p; i < p + 5; i++)
            sum *= i;
        
        while (sum)
        {
            if (sum % 10 == 0)
            {
                cnt++;
                sum /= 10;
            }
            else
                break;
        }
 
        if (p == n)
            break;
 
        p += 5;
 
        if (p > n)
            p = p + (p - n) - 5 + 1;
    }
 
    if (n % 100 == 50)
        cnt -= 1;
 
    printf("%d\n", cnt-1);
 
    return 0;
}

2. 힌트를 얻고 짠 코드

십진수를 생각보았더라면..

앞 문제(N!의 표현법)에서 했던 것과 같이 팩토리얼에 포함되는 각 숫자를 소인수분해한 후,

소인수분해 한 숫자들을 배열에 저장한다.

저장된 배열에서 2와 5의 개수를 비교해서 작은 개수가 원하고자하는 0의 개수가 되는 것이었다. 

만일 2가 10번, 5가 7번 사용되었다면 10^7 * 2^3 이 될 것이고 결국 0의 개수는 7개가 될 것이다.

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    //freopen("input.txt", "rt", stdin);
 
    int n, i, p, num, cnt;
 
    scanf("%d", &n);
    vector<int> v(n + 1);
 
    for (i = 2; i <= n; i++)
    {
        num = i;
        p = 2;
 
        while (num != 1)
        {
            if (num % p == 0)
            {
                v[p]++;
                num /= p;
            }
            else
                p++;
        }
    }
 
    cnt = v[2] > v[5] ? v[5] : v[2];
 
    printf("%d\n", cnt);
 
    return 0;
}

#. Other code

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main(){
    int n, i, j, tmp, cnt1=0, cnt2=0;
 
    scanf("%d", &n);
 
    for(i=2; i<=n; i++){
        tmp=i;
        j=2;
 
        while(1){
            if(tmp%j==0){
                if(j==2) cnt1++;
                else if(j==5) cnt2++;
 
                tmp=tmp/j;
            }
            else j++;
 
            if(tmp==1) break;
        }
    }
 
    if(cnt1<cnt2) printf("%d\n", cnt1);
    else printf("%d\n", cnt2);
 
    return 0;
}

우선 소인수분해된 수가 2인 경우와 5인 경우의 cnt를 단수히 변수로 얻어냈다..나는 N + 1 크기의 vector 를 사용했는데.. 

사실 다수의 원소를 알기 위한게 아니라 두 개의 원소만 알아내면 되었던 것이므로 배열을 굳이 사용할 필요는 없던 것 같다. 

하지만, 모든 과정에서 비교 연산을 수행하는 것도 속도 측면에서 좋은 것만은 아닌 것 같다. 

메모리를 줄이는 것이 목적인지 속도를 높이는 것이 목적인지에 따라 구현하는 방법도 달라지는 것 같다. 

#. Result

  - Input --------------------------------------------------------

12

------------------------------------------------------------------

  - Output --------------------------------------------------------

2

------------------------------------------------------------------