[baekjoon] 3474 교수가 된 현우 (javascript,c++)

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

3474번: 교수가 된 현우

---

알고리즘 : 수학? 시간복잡도?

 

n의 최대 크기가 10억이다...

보자마자 dp 문제일 것이라고 생각했으나 택도 없다!

 

고민 고민 하다가 결국 못풀어서 검색을 통해 알아봤다.

소인수 분해를 통해 2와 5의 개수 중 작은 것이 정답이라고 한다.

 

솔직히 소인수 분해가 뭔지 기억도 잘 안나고 이걸 문제를 풀면서 생각할 수 있을까? 라는 생각이 들었다 ㅜㅜ

이런 문제를 풀면서 다시 공부하고 나중에 혹시나 같은 문제가 나오면 풀 수 있겠지!!

 

하지만 같은 코드로 javascript 로는 시간 초과가 발생하고 c++로는 풀린다.

결국... javascript로는 못 푸는 문제로 결론을 내렸다.

 

백준은 정답을 맞추면 정답코드를 볼 수 있는데 javascript 정답코드를 써도 시간 초과가 발생한다.

 

코드는 누군가 도움이 될 수 있기 때문에 남겨둔다.

 

- Javascript

/**
 * 제출용. 아래 로컬용을 지우고 제출하자.
 */
//  let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n")
/**
 * 로컬용, 예제.txt를 생성해서 예제를 복붙하자.
 */
let input = require("fs")
  .readFileSync("input.txt") //"/dev/stdin"
  .toString()
  .split("\n")
  .map((val) => val.trim());


  let t = +input.shift();
  input = input.map(v=>+v);

function solution() {


  while(t--){
    let n = input.shift();

    let five = 0;


    for(let i=5;i<=n;i*=5){
      five+=Math.floor(n/i);
    }

    console.log(five);
   
  }

  
}

solution();

 

-C++

#include <bits/stdc++.h>
using namespace std;

int N,num;

int countZero(int num){
    int ret=0;
    for(int i=5; i<=num; i*=5){
        ret += num/i;
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> num;
        cout << countZero(num) << "\n";
    }
    return 0;
}