Sandor의 개발 일지

Make real your dreams

1 분 소요

Question

Q Q2

Solution

  • number까지의 약수의 개수를 구하고 limit를 적용하여 모두 합해야한다.
  • 이중 for루프를 이용하여 1~number까지 약수의 수를 구하도록한다.
  • count가 limit 보다 크면 power로 만들고 종료시 answer에 count를 더해준다.

주의! 약수를 구할땐 i % j == 0 이면 약수이지만 완전탐색시 O(N)의 시간복잡도를 가지기 때문에 시간초과가 발생한다.
따라서 제곱근까지 탐색하는 방법을 사용한다.
ex) i = 6 일때 약수는 1, 2, 3, 6 이다. (1일때와 2일때만 약수를 구하면 모두 구해지는 점을 이용한다.)
1 * 6, 2 * 3 이므로 나누어 떨어지때마다 count += 2를 해주되 예외가 있다.
i = 4 일경우 2 * 2 = 4가 되는 중복되는 수가 있기 때문에 해당 조건을 예외처리 해준다.

Cord

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 시간초과
int solution_TimeOver(int number, int limit, int power) 
{
    int answer = 0;

    // number까지 순서대로 탐색
    for (int i = 1; i <= number; ++i)
    {
        int count = 0; // i에 대한 약수의 수
        for (int j = 1; j * j <= i; ++j)
        {
            if (i % j == 0) { ++count; }
        }

        // count가 limit 보다 크면 power로 제한
        if (count > limit) { count = power; }
        answer += count;
    }

    return answer;
}

// 정답
int solution(int number, int limit, int power)
{
    int answer = 1; // 1의 약수는 항상 한 개

    // 2부터 number까지 순서대로 탐색
    for (int i = 2; i <= number; ++i)
    {
        int count = 0; // i에 대한 약수의 수

        // 자신 i의 제곱근까지 구하면 됨
        // 6 = 1 * 6, 2 * 3 -> 1, 2, 3, 6
        for (int j = 1; j * j <= i; ++j)
        {
            if (j * j == i) { ++count; } // 제곱수 중복 예외처리
            else if (i % j == 0) { count += 2; }
        }

        // count가 limit 보다 크면 power로 제한
        if (count > limit) { count = power; }
        answer += count;
    }

    return answer;
}

int main()
{
    int number = 5;
    int limit = 3;
    int power = 2;

    int answer = solution(number, limit, power);
    cout << answer;

    return 0;
}

Result

Result

참고