9. 모두의 약수

    9번 문제   

 

 

    내가 풀이한 답   

 

  처음에는 간단히 모든 수를 돌며 그 수에 해당하는 수까지 또 돌아서 약수를 구하는 방식으로 코드를 짰다. 즉, 모든 수를 다 돌기 때문에 N제곱의 시간복잡도가 나온다. 

#include <stdio.h>
using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	
	int n, i, j, cnt=0;
	scanf("%d", &n);
	
	for(i=1; i<=n; i++) {
		cnt=0;
		for(j=1; j<=i; j++){
			if(i%j==0){
				cnt++;
			}
		}
		printf("%d ", cnt);
	}
	printf("\n");
}

 

 그 결과는 60점에 큰 숫자로 들어가버리면 시간 초과가 뜬다... (Time Limit: 1초)

 

 

 더 곰곰히 생각해보다가 더 이상 떠오르질 않아서 강의 초반부에서 전략을 들었다. 모든 경우의 수를 다 도는 것은 비효율적이므로 어차피 약수를 구하는 것은 배수의 개념으로도 풀 수 있다고 말하였다. 다시 머리를 한 대 얻어맞은 듯한 느낌을 받았다. 강의의 내용은 다음과 같다. 순회(for)를 돌면서 해당하는 값의 배수들만 값을 증가시켜주는 방법이다. 

 

 

 

#include <stdio.h>
using namespace std;
int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	int array[50001];
	int n, i, j;
	scanf("%d", &n);
	
	for(i=1; i<=n; i++) {
		for(j=i; j<=n; j=j+i){
			array[j]++;
		}
	}
	
	for(i=1; i<=n; i++){
		printf("%d ", array[i]);
	}
}

 

 그 결과 80점... 왜 그럴까.. 하고 사이트의 답안과 비교해봤다. 

 

 

    사이트의 답안   

#include<stdio.h>
using namespace std;
int cnt[50001];
int main(){
	//freopen("input.txt", "rt", stdin);
	int n, i, j;
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		for(j=i; j<=n; j=j+i){
			cnt[j]++;
		}
	}
	for(i=1; i<=n; i++){
		printf("%d ", cnt[i]);
	}
	return 0;
}

 

  사이트의 답안과 내 코드는 배열을 선언한 부분의 전역인지 지역인지의 차이였다. 지역변수와 전역변수의 차이점에 대해 조사를 해봐야겠다...