[백준 알고리즘 C/C++] 3474번 문제 풀이: 교수가 된 현우

** 이 글을 읽음에 앞서 포스팅 된 소스가 100% 정답은 아님을 밝힙니다.

    더욱 유능한 분께서 클린 / 최적의 소스를 짜셨을 가능성이 높습니다.

    기록용으로 남기며, 참고만 부탁드립니다.

** 백준 알고리즘은 직접 풀이를 해보시는 것을 권장합니다.

---

● 문제

난이도[티어] : 실버 3

백준 알고리즘 3474번 교수가 된 현우

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

3474번: 교수가 된 현우

---

● 풀이 방법

오른쪽 끝에 0의 개수가 생기는 경우는 2와 5가 곱해 졌을 때, 0이 생성이 된다.

즉 입력 받은 값을 소인수분해를 하여 2와 5의 개수를 확인하여 2와5가 곱해지는 경우를 따지면 된다.

2는 항상 5보다 개수가 많으므로, 소인수 분해시 5의 개수를 확인하여 출력하면 된다.

 

예시를 들자면, 숫자 60이 주어졌다.

60의 경우 소인수 분해시

60/5 = 12개

60/25 = 2개

60/2 = 30개... [ 2의 소인수 분해 개수 값은 5보단 많으니 생략.]

 

결국 12 + 2 해서 14라는 결과가 나오게 된다.

---

● 소스 코드

#include <iostream>

using namespace std;

int main()
{
	//연산속도 개선을 위한 식
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int test_case, num;
    cin >> test_case;
    for(int i = 0; i < test_case; i++){
        int sum = 0;
        cin >> num;
        // 소인수 분해 시 5의 개수를 확인하는 식
        for(int j = 5; j <= num; j *= 5)
            sum += num / j;
        cout << sum << "\n";
    }
    return 0;
}

 

생각보다 시간초과가 되는 경우가 많아서 개선을 위한 식 3줄이 들어갔다.

위 3줄의 식에 관련해서는 따로 포스팅을 할 예정이다.

 

소인수 분해 숫자는 2와 5의 개수를 체크해서 확인해야 하는데

2의 경우 5의 개수보다 훨씬 많기에 연산을 하지 않았다. 

2까지 추가 할 경우에는 시간초과가 뜰 가능성이 있기 때문에 5의 개수로만 판단해서 출력했다.

---

● 결과

** 코드 길이가 상이 할 수 있습니다! 그러나 내용물은 같습니다.

    이유)  주석 및 더미 소스 유무

 

시간초과 에러가 상당했다..!