JArchive 프로그래밍 일기

문제 

자연수 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;
}

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