9. 모두의 약수

고줭 2021. 5. 12. 13:28

문제

자연수 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까지 약수의 개수를 순서대로 출력한다.

입력예제

출력예제

1 2 2 3 2 4 2 4

#include <stdio.h>
using namespace std;

int count[50001];

int main(){
	freopen("input.txt", "rt", stdin);
	int i, j, n;
	scanf("%d", &n);
	
	for(i=1; i<=n; i++){
		for(j=i; j<=n; j=j+i){
			count[j]++;
		}
	}
	
	for(i=1; i<=n; i++){
		printf("%d ", count[i]);
	}
	
	return 0;
}

저는 이런 문제를 풀기위해서 이중for문을 생각하는데 단순한 이중for문은 N^2의 시간복잡도를 가질 확률이 높습니다.
시간초제한은 1초이며 N은 최대 50,000까지기에 경우의수를 최대로 줄이는것이 중요합니다.

정답의 문제풀이는 j for문에서 j=j+i로 i=3일때 j는 3의 배수의 배열에 count++하는겁니다. 이것만으로도 엄청난 시간복잡도를 줄일수있습니다.

저는 항상 for문을 작성할때 i=0을 생각합니다 위와 같은 상황에서 i=0으로 할수없을까? 하고 이리저리 만져봤는데 무한루프에 빠지게되고 애초에 count배열을 출력할때도 0번인덱스의 것은 출력하지않고 1번 인덱스부터 출력하기에 굳이 i=0으로 하지않는것이 좋다고 생각합니다.

혼자 풀때 count배열을 지역변수로 설정했는데 채점프로그램에서는 5번예제에서 틀린답이 나왔습니다. 인프런 커뮤니티에서도 저와같은 질문을 하신분이계셔서 읽어보니까 지역변수로 설정시에 배열이 크면 값이 0으로 초기화되지 않을경우가 있다고합니다. 이에 지역변수로 하려면 0으로 초기화하는 코드를 작성하거나 전역변수로 설정하는것이 정확하다고 합니다.

답변

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

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

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

그리고 벡터를 사용하는것이 좋다고 합니다.

벡터만능주의.

모두의약수 모두해~