프로그래머스 문제, 기사단원의 무기

문제파악

<입력된 값의 범위>

기사단의 수 : 1 <= number <= 100,000

공격력 제한 수치 : 2 <= limit <= 100

협정 공격력 수치 : 1<= power <= limt

 

약수의 수를 찾는 문제라고 생각했다. 때문에 약수를 찾는 제일 빠른 방식에 대해 고민을 해보았다.

전개

내가 알고 있는 약수들의 집합의 특징은 정수인 제곱근을 기준으로 대칭형이라는 점이다. 제곱근이 정수라면 홀수개, 정수가 아니라면 짝수개.

 하지만 수가 커질수록 하나하나 대입해 보아 약수를 찾는 것은 무리라고 생각했다. 100,000의 제곱근이 316이 조금 넘는데 100,000에 근접한 숫자들을 대략 300까지 매번 약수인지 찾아본다면 당연히 시간의 문제가 생길 것이라고 생각했다.

 다음으로 생각한 방식은 소인수 분해이다. 소수를 활용해 소인수 분해를 한다고 가정하면 검색하는 소수가 많아질수록 메모리를 쓰는 양이 많아질 것 같았다. 소인수분해를 대상에 가까운 소수까지 계산한다고 하면, 최대 100,000에 근접한 소수까지 대입하게 되는데 이 역시 말도 안된다.

그래서 약수 집합의 특징을 활용해 보고자 했다. 소인수 분해를 얘기하고 있지만 결국 나오는 소수가 약수인 것은 분명하다. 따라서, 소인수로 나올 수 있는 수는 제곱근 이전까지 나온 소수 혹은 소수들과의 곱으로 원래 수를 표현하게 된다. 제곱근 이하의 수로 나누어 지지 않는 수는 소수일 확률이 높겠다는 생각이 들기도 한다.

 아무튼 이렇게 소인수 분해로 나온 숫자들을 조합한다면 모든 약수의 개수를 찾는 것은 어려운 것이 아니다. 하지만 최대 316 이하의 소수 역시 수의 개수 역시 좀 많다. 물론 316까지 생짜로 계산하는 것보다 당연히 양은 줄었다고 생각했다. 하지만 나누는 수가 소수인지 아닌지를 매번 확인하고 이를 나누는지 아닌지를 계산하는 것은 그만큼 부담을 늘린다고 생각하고 다시 보니 limit 값이 눈에 들어왔다.

 결론적으로 이 문제는 약수를 찾는 문제는 맞지만 limit개가 넘어갔을 때는 굳이 계산할 필요없이 power로 그 값을 대체하는 방식이다. limit 값은 약수 집합의 특성과 결합하면 다음과 같은 결론을 내릴 수 있다.

- 현재 계산하고 있는 수의 제곱근 이하의 약수의 수와 limit의 절반값과 비교한다면 limit을 넘었는지 아닌지를 판단할 수 있다.

고민사항

어짜피 1부터 number까지의 수에 대해 약수의 수를 찾기 때문에  1부터 반복된다. 결국 같은 수가 반복되기 마련이니 전역변수로 활용하고 싶긴 하지만 일단 위의 내용 정도로만 구현하고자 한다.

소스코드

#include <string>
#include <vector>

using namespace std;

int solution(int number, int limit, int power) {
    int answer = 1;
    for(int i = 2;i <= number;i++){
        int div_num = 2;
        for(int j = 2;j*j<=i;j++){
            if(j*j == i) div_num++;
            else if(i%j == 0) div_num = div_num + 2;
            
            if(limit<div_num){
                div_num = power;
                break;
            }
        }
        answer += div_num;
    }
    return answer;
}