오늘의 문제는 약수의 개수를 구하는 것이다. 근데 이게 단순히 어떤 숫자를 입력했을 때 그 숫자의 약수의 개수를 구하는게 아니라, 만약 100을 입력하면, 1부터 100까지의 모든 숫자의 약수를 구해서 출력해 주는것이다.
런타임 제한이 1초라고 써져있는 것을 보고, 당연히 의구심이 들기는 했지만, 일단 너무나 자연스럽게 처음에는 다음과 같은 코드로 짰다.
#include<iostream>
using namespace std;
int main(){
int N,cnt;
cin>>N;
for(int i=1; i<=N; i++){
cnt=0;
for(int j=1; j<=i; j++){
if(i%j==0){
cnt++;
}
}
cout<<cnt<<" ";
}
}이렇게 코드를 짰을 경우, N(입력값)이 한 2000? 정도면 런타임 1초안에 나오지만, 20000이상으로 넘어갔을 경우네는, 런타임 초과로 오답이 된다.
그래서 생각보다 고민을 많이 했지만, 스스로 생각해 내지 못하고 결국 강의를 봤다.
강의를 듣고 다시 짜본 코드는 다음과 같다.
#include<iostream>
using namespace std;
int main(){
int cnt[50001];
int i, j, N;
cin>>N;
for(i=1; i<=N; i++){
for(j=i; j<=N; j = j + i ){
cnt[j]++;
}
}
for(i=1; i<=N; i++){
cout<< cnt[i]<<" ";
}
}일단, 제일 중요한건 A라는 숫자가 있을 경우, A*n 은 무조건 A를 약수로 갖는다. 이 개념을 토대로 cnt라는 배열을 만들어줘서, 포문을 돌리면서 자신의 배수 배열칸에 1씩 증가시키며 약수의 개수만 파악한다.
이처럼, 약수를 일일히 다 구하는 것이 아니라, 정말 말그대로 약수의 '갯수'만 파악해준다.
이렇게 해줄 경우, 처음 내 코드의 시간복잡도는 n^2 이었지만, 두번째 코드의 시간복잡도는 n^2에 비해 훨씬 줄어든다. 왜냐하면 두번째 for문의 j가 계속 i 씩 늘어나기 때문이다.
항상 for문을 쓸 때, i를 단순히 하나씩 증가시키거나, n만큼 증가시켜주곤 했는데, 이중 for문으로 첫번째 i만큼 증가시켜주는 for문은 이번에 처음 써본다. 굉장히 기발한 생각이고 앞으로도 유용하게 써야겠다.
아 그리고 마지막으로 중요한건, 지금 저 두번째 코드로 실행할 경우, N값이 50000이면 오답이 뜬다. 아마 그 이유는, 현재 입력과 출력을 cin 과 cout으로 해서 그런것 같다. 강의에서도 그랬지만, 숫자의 양이 크거나 많을 경우 cin 혹은 cout으로 할 경우, 시간이 좀 오래 걸린다거나, 오류가 날 수도 있다고 했다. 따라서 웬만하면 c++의 입출력 방식(?) 이 아닌 &을 이용한 입출력 방식을 사용해야겠다.
