[BOJ_3474 | Number Theory] 교수가 된 현우

풀이 문제 자체는 크게 어려운 문제는 아니었던것 같다.하지만, 풀이 과정에 따라서 시간 복잡도가 천차만별이 될 수 있다는 것을3번의 실패끝에 경험했다. 몇 자리수인지를 물어보는 것이 아니라 뒷자리에 0이 몇개가 있는지를 계산하는 문제였기 때문에비교적 간단하게 2 와 5의 개수만으로 답을 구할 수 있다. 단 이때 참고해도 될 만한 부분은 1. 2의 개수는 무조건 5의 개수보다 많으므로 굳이 2의 개수를 세느라 시간을 낭비할 필요가 없다 2. 1~N 사이의 2나 5의 배수를 탐색하는 과정에서 모든 숫자를 탐색할 필요가 없다 이 2가지 정도로 정리할 수 있겠다. 2번을 몰랐던 상황에서 1024!의 값을 구하기 위해1~1024 까지의 모든 자연수의 2, 5의 배수개수를 세고 있었고결과적으로 시간 복잡도가 증가하..

2019.01.02