[백준2004] 조합 0의 개수 (C++)
시간초과 코드
#include <iostream>
using namespace std;
int func2(int);
int func5(int);
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n; cin >> m;
int num = min(func2(n) - (func2(n - m) + func2(m)), func5(n) - (func5(n - m) + func5(m)));
cout << num;
return 0;
}
int func2(int x) {
int count = 0;
while (x>0) {
int k = x;
while (1) {
if (k % 2 == 0) {
count++;
k /= 2;
}
else
break;
}
x--;
}
return count;
}
int func5(int x) {;
int count = 0;
while (x > 0) {
int k = x;
while (1) {
if (k % 5 == 0) {
count++;
k /= 5;
}
else
break;
}
x--;
}
return count;
}
과도한 반복문 사용으로 시간초과가 뜨는 코드이다.
구글링의 힘을 빌려 코드를 다시 짜 보았다.
#include <iostream>
using namespace std;
long long func2(long long);
long long func5(long long);
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
long long n, m;
cin >> n; cin >> m;
long long num = min(func2(n) - (func2(n - m) + func2(m)), func5(n) - (func5(n - m) + func5(m)));
cout << num;
return 0;
}
long long func2(long long x) {
long long count = 0;
for(long long i = 2; i <= x; i *= 2)
count += x / i;
return count;
}
long long func5(long long x) {
long long count = 0;
for (long long i = 5; i <= x; i *= 5)
count += x / i;
return count;
}
int 자료형을 long long 자료형으로 바꿔주고 구현 방식을 달리했다.
100!에 5가 몇 개 들었는지 파악하기 위해 이전 방법처럼 1부터 100까지의 숫자를 5로 나눌 수 있는 횟수를 더해주는 방법을 사용할 수도 있지만 가장 간단한 방법은 100을 5, 5^2로 나는 몫을 더해주는 것이다.
100=5*20
100=25*4
따라서 20+4=24
상당히 간편한 방법이다. 기억해두는 편이 좋을 것 같다.
Author And Source
이 문제에 관하여([백준2004] 조합 0의 개수 (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yoohoo030/백준2004-조합-0의-개수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)