[C++로 풀이] 숫자 블록 (소수) ⭐⭐⭐⭐

📌 숫자 블록

난이도 ⭐⭐⭐⭐

🚀 문제

🚀 내 풀이 ⭕

자기 자신을 제외하고 10,000,000 을 넘지 않는 선에서의 가장 큰 약수

18 의 약수는 1, 2, 3, 6, 9, 18 이다. 18 번 도로에 설치되는 블록은 9 번 블록이 된다.(n 번 블록은 n * 2 번 도로부터 설치가 되기 때문) 즉, 약수들 중 자기 자신을 제외한 수들 중에서 가장 큰 수의 블록이 설치 되는 것이다. 자기 자신을 제외한 가장 큰 약수의 짝꿍은 1 을 제외한 가장 작은 약수가 된다.(즉 이 경우엔 2 가 된다. 18 / 9 는 2 이다.) 이 가장 작은 약수를 구해서 도로 위치에서 나눠주면 자기 자신 제외 가장 큰 약수를 구할 수 있게 된다.(아무래도 뒤에서부터 검사하는 것 보단 앞에서부터 검사하는게..⭐ 게다가 sqrt(도로 번호) 까지만 검사하면 된다. 약수 짝꿍의 기준이 되는 곳이기 때문)

다만, 약수가 1 과 자기 자신을 제외하고는 없는 소수들의 경우에는 자기 자신 제외 가장 큰 약수가 없으므로 1 을 추가해주면 된다. 1 번 블록 말고는 다른 블록이 설치될 일이 없기 때문.

주의해야할 사항이 하나 더 있는데, 블록의 번호는 최대 10,000,000 까지만 있다는 것이다. 즉, 설치할 수 있는 블록은 10,000,000 번 블록까지이기 때문에 자기 자신을 제외한 가장 큰 약수가 10,000,000 를 넘는 경우엔 설치될 수가 없다. 따라서 이런 경우엔 10,000,000을 넘지 않는 것 중에 가장 큰 약수를 찾아야 한다.

또! 주의해야할 사항이 있는데, begin 이 1 이라면, 즉 1 번 도로에 어느 블록이 최종적으로 설치되는지도 구해야할 땐, 1 번 도로는 항상 0 번 블록이 설치되므로 0 을 삽입해준다.

#include <string>
#include <vector>
#include <cmath>

using namespace std;

vector<int> solution(long long begin, long long end) {
    vector<int> answer;
    for(int num = begin; num <= end; ++num){
        if (num == 1){
            answer.push_back(0);
            continue;
        }
        bool found = false;
        // 1️⃣ 처음으로 num % i == 0 가 되는 경우 -> i 는 가장 작은 약수. 고로 num / i 는 자기 자신을 제외한 가장 큰 약수가 된다. (i 의 짝꿍 약수)
        // 2️⃣ 만약 num / i 가 (자기 자신 제외 가장 큰 약수) 10,000,000 을 넘는다면 자연스럽게 다음 반복을 통해 더 커진, 증가된 i 부터 검사해나가면 된다. i 가 증가하면 num / i 는 감소한다. 이렇게 10,000,000 을 넘지 않는 선에서의! 가장 큰 약수를 구하면 된다.(num/i 가 10,000,000 을 넘지 않으면서 동시에 약수가 최는 최초의 수)
        for (int i = 2; i <= sqrt(num); ++i){
            if (num % i == 0 && num / i <= 10000000){
                answer.push_back(num / i);
                found = true;
                break;
            }
        }
        // 소수이거나 
        // sqrt(num)이하 약수의 짝꿍들이 모두 10,000,000 보다 큰 수 
        // 즉, 위 for문의 if 에 한번도 걸린적이 없음
        if (!found) 
            answer.push_back(1);
    }
    return answer;
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기