모두의 약수 (제한시간 1초)

문제 

자연수 N이 입력되면 1부터 N까지의 각 숫자들의 약수의 개수를 출력하는 프로그램을 작성하세요.

만약 N이 8이 입력된다면 1(1개), 2(2개), 3(2개), 4(3개), 5(2개), 6(4개), 7(2개), 8(4 개) 와 같이 각 숫자의 약수의 개수가 구해집니다.

출력은 다음과 같이 1부터 차례대로 약수의 개수만 출력하면 됩니다.

1 2 2 3 2 4 2 4 와 같이 출력한다.

 

입력설명 

첫 번째 줄에 자연수 N(5<=N<=50,000)가 주어진다.

 

출력설명

첫 번째 줄에 1부터 N까지 약수의 개수를 순서대로 출력한다

 

 

 

풀이 

 

이중 반복문을 이용해서 숫자 마다의 약수를 구하려고 했었다. 

하지만 그렇게 하면 시간초과가 난다. 

그래서 약수의 개수를 for문을 순회할 때마다 +1 해주는 방식이 필요하다. 

 

"1을 약수로 갖는 숫자들은 어떤 숫자들일까?"
"1의 배수들이다."

"2을 약수로 갖는 숫자들은 어떤 숫자들일까?"
"2의 배수들이다."

2의 배수들은 2를 약수로 갖는다. 

이 점을 이용한 것이다. 

 

1은 모든 수의 약수이므로 배열 모든 칸에 +1을 해준다. 

2는 모든 짝수 들의 약수이므로 2의 배수에 해당하는 칸에 +1을 해준다. 

. . . 

내부 for문을 이렇게 구현한다. 즉, j는 i로 시작하되, i의 배수이니까 j는 j+i만큼 커지면서 배열을 건너뛰어가면서 배수를 인덱싱한다. 

 

 

 

궁금한 점 

 

50001 크기의 int 배열 cnt는 지역변수 인 경우에 테스트케이스에서 fail이 난다. 

그런데 cnt가 전역변수 인 경우에는 테스트케이스를 전부 통과했다. 

그 차이가 뭔지 궁금했다. 

 

#include <stdio.h> 

int cnt[50001];

int main(int argc, char** argv) {
	
	//freopen("input.txt", "rt", stdin);
	int input=0, i=0, j=0;
	scanf("%d", &input);
	
	for(i=1; i<=input; i++){
		
		// i의 배수들을 +1 처리해준다. 
		// i를 약수로 갖는 숫자들을 찾는 것이다.  
		for(j=i; j<=input; j=j+i){
			cnt[j]++;
		}
	}
	
	for(i=1; i<=input; i++){
		printf("%d ", cnt[i]);
	} 

	return 0;
}

 

선생님이 답변을 달아주셨다. 

배열선언에서 지역변수와 전역변수의 차이는 대략 2가지 정도입니다.

1. 배열을 전역으로 선언하면 기본값이 0으로 초기화 됩니다. 하지만 지역변수는 0으로 초기화 된다는 보장이 없습니다. 지역변수로 선언할 때 0으로 확실이 초기화 하고 싶으면 int cnt[50001]={0, } 이렇게 선언하면 됩니다.

 

2. 지역변수로 선언하면 메모리의 스택영역에 할당됩니다. 스택을 메모리가 작어 크기가 큰 배열을 선언하기에는 적당치 않습니다. 전역변수는 메모리의 데어터 역영에 할당되며, 크기가 큰 배열을 선언해도 문제없이 할당이 됩니다. 즉 문제풀이 코드에서는 크기가 10만 이상 크기의 배열은 전역으로 선언하는게 좋습니다.

 

위 코드의 문제는 지역변수로 선언해서 0으로 초기화가 되지 않아서 생기는 에러같습니다.

 

22번 문제와 24번 문제에서 벡터를 사용해 배열을 동적으로 선언하는 것을 배웁니다. 벡터을 사용하는게 제일 좋습니다.