[Programmers] Lv2. 숫자 블록 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

• n번째 블록에 놓여질 숫자는 n이 소수일 경우엔 1, 아닐 경우에는 10,000,000보다 작은 제일 큰 약수입니다.
• 제곱근 방식을 이용하여 약수와 소수를 찾는 데에 시간을 효율적으로 절약할 수 있습니다. 현재 점검하려는 숫자를 i라고 한다면,
  • n / i \( \leq 10,000,000 \) 이라면, n / i가 가장 큰 약수가 됩니다. 가장 큰 약수를 찾았으므로 반복문을 종료합니다.
  • 아니라면, i를 선택한 후에 다음 루프로 넘어가도록 합니다.
• n이 1인 경우에는 0이 적힌 블록이 있어야 하므로, 이 부분만 예외 처리를 해주도록 합니다.

 

블록 숫자가 10,000,000보다 크면 안 된다는 점에서 많이 헤맸던 문제인 것 같습니다.

 

✏️소스 코드 및 결과

#include <vector>
using namespace std;
const int MAX_VALUE = 10000000;

long long FindMaxDivisor(long long n) {
    long long result = 1;

    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            result = i;

            if (n / i <= MAX_VALUE) {
                result = n / i;
                break;
            }
        }
    }

    return result;
}

vector<int> solution(long long begin, long long end) {
    vector<int> answer;

    for (long long i = begin; i <= end; i++) {
        if (i == 1) {
            answer.emplace_back(0);
            continue;
        }
        answer.emplace_back(FindMaxDivisor(i));
    }

    return answer;
}