문제
자연수 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까지 약수의 개수를 순서대로 출력한다.
💡 입력예제
8
💡 출력예제
1 2 2 3 2 4 2 4
코드
첫 번째 풀이
#include <stdio.h>
int main() {
int n, i, j, cnt;
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);
}
return 0;
}최종 풀이
#include <stdio.h>
int main() {
int n, i, j;
scanf("%d", &n);
int a[n];
for(i = 1; i <= n; i++) {
a[i] = 0;
}
for(i = 1; i <= n; i++) {
for(j = i; j <= n; j = j + i) {
a[j] += 1;
}
}
for(i = 1; i <= n; i++) {
printf("%d ", a[i]);
}
return 0;
}
설명
사용자로 부터 n을 입력닫는다.
n의 약수는 배수로 이루어져 있으므로 n크기의 배열에서 1~n의 배수에 해당하는 index에 cnt를 1씩 증가하도록 한다.
1~n까지 반복하는 for문을 작성하고 i를 시작으로 배수 만큼 커져야 하므로 j = j + i만큼 증가하는 for문을 작성하여 배열의 j index를 1씩 증가하도록 한다.
마지막으로 배열의 cnt를 출력하는 for문을 작성하여 마무리한다.
배운 점
처음 2중 for문으로 i % j == 0으로 조건으로 1~n까지 모두 순회하는 코드를 작성하여 time limit가 발생하였다. 하지만 약수는 배수로 이루어져있다는 개념을 적용하면 배수만큼 증가면서 순회하는 for문을 작성할 수 있었고 이는 기존의 O(n^2)의 시간복잡도로 인한 time limit 오류에서 벗어날 수 있었다.
해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.
