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

dldzm·2021년 6월 28일
0

알고리즘 공부

목록 보기
42/42
post-thumbnail

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

문제 읽기

팩토리얼 계산하고 뒤의 0을 계산하자

  1. 팩토리얼을 계산하고 string으로 바꿔서 string의 size-1 위치부터 접근해서 0과 비교하자 -> string을 index로 접근하여 비교할 수 없음 -> char로 접근하려고 했지만 const char* 로 인해 접근하지 못했음
  2. 팩토리얼을 계산하고 5와 2로 나눌 수 있다면 그 수를 count하여 5와 2의 개수 중에 최소 수를 내보내자 -> 시간 초과
  3. 애초에 팩토리얼 계산을 하지 말고 팩토리얼에서 곱해지는 숫자들을 5와 2로 나눠 누적 계산하자 => 완료

코드

try 1

#include <iostream>
using namespace std;


int factorial(int n) {
    int result = 1;
    for (int i = n; i > 0; i--) {
        result = result * i;
    }
    return result;
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int num;
    int cnt = 0;
    cin >> num; 
    int q = factorial(num);
    int r = 0;
    while (true) {
        r = q % 10;
        if (r == 0) {
            cnt++;
            q = q / 10;
        }
        else { 
            cout << cnt; 
            return 0;
        }
    }
}

try 2

#include <iostream>
using namespace std;

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int num, cnt5 = 0, cnt2 = 0;
    cin >> num;    

    for (int i = num; i > 0; i--) {
        int rs = i;
        int tmp = i;
        while (true) {
            if (rs % 5 == 0) {
                cnt5++;
                rs = rs / 5;
            }
            if (rs % 2 == 0) {
                cnt2++;
                rs = rs / 2;
            }
            if (tmp == rs)
                break;
            else {
                tmp = rs;
            }
        }
    }

    if (cnt2 > 0 && cnt5 > 0)
        cout << min(cnt5, cnt2);
    else
        cout << 0;
    return 0;
}

분석

반복 계산이 들어가면 시간이 엄청나게 증가한다. 500!을 계산한다면 우선 int가 못받아들인다. long long int로 접근하던가 했어야 했고.

팩토리얼 계산을 하지 말고 어차피 다 곱해지는 것이었으므로 곱해지는 요소를 분석하여 계산시간을 줄이는 것이 중요했다.

profile
🛰️ 2021 fall ~

0개의 댓글