[백준 1241번] 머리 톡톡 (C++)

https://www.acmicpc.net/problem/1241

 

이 문제는 순서가 있는 것 처럼 보이지만 사실은 순서가 전혀 중요하지 않은 문제이다.

 

i번 숫자가 원을 돈다고 할 때 결국 지금 이 숫자가 내 약수인가? 라는 것이 문제이고 곧 이 숫자의 약수가 배열에 몇개가 있는가?

 

라는 것을 물어보는 문제이다.

 

그렇다면 시간복잡도 = O (약수를 구하는 시간 복잡도 * N) 으로 결정할 수 있다.

 

효율적으로 약수를 구하는 방법을 사용하면 O(Root(N)) 으로 해결할 수 있다. 

 

36의 약수를 구한다고 해보자. 초등학생의 방법을 사용하면 1부터 36까지 모두 나누어보면 된다. 그렇다면

 

1, 2, 3, 4, 6, 9, 12, 18, 36 이 나온다. 벌써 느낌이 올 것이다. 19부터 35까지는 쓸대없는 계산으로 시간을 낭비하게 된다. 

 

그래서 우리는 1~N까지가 아닌, 1 ~ Root(N) 까지 나누어준다.

 

그렇다면 

 

1, 2 ,3, 4, 6 

 

이러면 남은 9이상은 구할 수 없다. 이제 구한 이것으로 N을 나누어보자

 

36 / 1 = 36
36 / 2 = 18
36 / 3 = 12
36 / 4= 9
36 / 6 = 6

 

와! 나누어보니 남은 약수를 구했다. 단, 6은 중복으로 구해버렸다. 그래서 만약 구한 약수가 Root(N) 이라면 나누지 않는다.

 

이것을 코드로 바꾸어보면 다음과 같다. 

 

int main(){
    vector<int> vec;

    for(int i = 1; i <= sqrt(36); i++){
        if(36 % i == 0) {
            vec.push_back(i);
            if(i * i != 36) {
                vec.push_back(36 / i);
            }
        }
    }

    sort(vec.begin(), vec.end());

    for(int i : vec) {
        cout << i << ' ';
    }
}

 

 

그리고 이것을 알고 있다면 이 문제는 

 

10만 * Root(백만) 으로 약 1억으로 문제를 풀 수 있다. 

 

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;

int num[1000001];

vector<int> vec(100001);

int main(){
    int N; cin >> N;

    for(int i = 0; i < N; i++){
        cin >> vec[i];

        num[vec[i]]++;
    }

    for(int i = 0; i < N; i++){
        int ans = 0;

        for(int j = 1; j <= sqrt(vec[i]); j++){
            if(vec[i] % j == 0){
                ans += num[j];
                if(vec[i] != j * j){
                    ans += num[vec[i] / j];
                }
            }
        }

        cout << ans - 1<< '\n';
    }
}