[Inflearn] 모두의 약수

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. N이 최대 50,000 이므로 무식하게 풀면 이중 반복문이 되어 N^2(2,500,000,000) 의 시간복잡도가 나오므로 시간 초과가 되어버린다.

  2. N까지 i 의 약수가 무엇이 있을까? 생각하는 것 보다는, i를 약수로 갖는 수는 무엇이 있을까? 반대로 생각해보자.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

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

cs

#. Other code

#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;
}

(5) 전역변수로 선언하는 이유는, 원소를 자동으로 0으로 초기화시켜주기 때문

#. Result

  - Input --------------------------------------------------------

8    

------------------------------------------------------------------

  - Output --------------------------------------------------------

1 2 2 3 2 4 2 4

------------------------------------------------------------------