백준, BOJ, 1037번 C++ [CPP]

이문제는 내가 개똥같이 풀었다..

하지만 감은 어느정도 왔었다.

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

 

 

---

 

시간도 넉넉하다. 메모리도 넉넉하다.

long long을 쓸 것 같다는 생각을 하자.

 

#맞는 풀이

#include<iostream>
#include<vector>
#define M 1000000

using namespace std;


//약수 개수
int func(int a){
    int cnt = 0;
    for(int i =2; i<a; i++){
        if(a%i == 0)cnt++;
    }
    return cnt;
}

vector<int> vec; // 진짜약수가 들어있는 벡터

int main(){
    int num;
    cin >> num;
    
    for(int i =0; i<num; i++){
        int a;
        cin >> a;
        vec.push_back(a);
    }
    int ans = 0;
    for(int i = 2; i<=M; i++){
        int cnt = 0;
        for(int k : vec){
            if(i%k != 0)break; // i가 약수의 배수가 아니면
            if(i<=k) break; // i가 약수보다 작으면
            if(i%k == 0){
                cnt++; // 약수의 개수를 셈0
            }
        }
        if(cnt == num){
            if(num == func(i)){
              ans = i;
            break; // for문 더 돌필요 없음  
            }
        }
    }
    
    cout << ans << '\n';
    
}

 

솔직히 N을 소인수 분해 했다면

당연히...

가장 작은 약수와 가장 큰 약수를 곱하면.. 원래 수가 나와야 한다.

ㅋㅋㅋ

그걸 알고 있었지만..

 

 

시간과 메모리를 보아하니..

bruteforce가 아닌가 싶어..그냥 무식하게 계산했다.

 

func(i)는 시간이 많이걸리는 함수이므로 이중 조건문에서 안의 조건에 넣어줘야 시간을 벗어나지 않는다.

 

다시 정리하자면 나는 bruteforce로 풀었지만

 

다시 푼다면

진짜 약수를 입력받았다면

sort후

첫번째 약수와 마지막약수의 곱을 출력으로 냈을 것이다..