A60. 기사단원의 무기

문제

숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고(limit), 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력(power)을 가지는 무기를 구매해야 합니다.

풀이 구상

문제 자체는 이해하기 쉽다.
1부터 n까지의 약수 개수를 구하고, 이게 limit을 넘으면 power를, 아니라면 약수 개수를 그대로 구해서 answer에 더해주면 된다.

문제는, 이 문제는 runtime 싸움이라는 것이다.
약수를 구하는 방법은 이하 3단계로 진행되었다.

약수는 나머지가 0인 수이다 : 1부터 n까지 전부 계산

가장 직관적인 아이디어다.
약수라 함은 n을 나누었을 때 나머지가 0인 수이므로, for문을 통해 1부터 n까지 모든 정수에 대해 나누었을 때 나머지가 0인 수를 구하면 된다.

코드는 간단한데,
count_divisor라는 별도의 함수를 만들어서
임의의 숫자형 n을 받, 1부터 n까지 정수를 전부 돌려서 n%i==0인 경우에만 cnt에 1을 더해준다.
그리고 cnt를 return

이걸 solution 함수에서 1부터 number까지 모든 정수에 대해 실행한다.

def count_divisor(n):
    cnt = 0
    for i in range(1, n+1):
        if n % i == 0:
            cnt += 1
        else:
            pass
    return cnt

def solution(number, limit, power):
    answer = 0
    for i in range(1, number+1):
        atk = count_divisor(i)
        if atk > limit:
            atk = power
        answer += atk
    
    return answer

다만 이 문제는 1부터 number까지의 수에 대해, 각각 1부터 n까지 수행한다는 점에서, $\sum n^{2}$번 수행된다는 단점이 있다.

본인 제외 약수의 최대는 n/2를 넘을 수 없다 : 1부터 n/2까지 계산

약수의 구성을 생각해보면, 간단한 방법으로 횟수를 크게 줄일 수 있는 방법이 있다.
약수는 나누었을 때 나머지가 0인 수인데, 그렇다면 1을 제외하고, 그 다음인 2로 나누는 경우 (나누어 떨어지든 아니든) 몫은 n/2가 된다.
이를 다시 말하면, n/2보다 큰 수 중에는 n을 제외하고 n의 약수가 될 수 있는 수가 없다는 것이다.
즉, 애초에 약수를 구할 때 n까지 돌릴 것도 없이 n/2까지만 돌리고, 마지막에 n 본인을 세기 위해 cnt += 1만 해주면 연산량을 줄일 수 있다.

def count_divisor(n):
    cnt = 0
    for i in range(1, (n//2)+1):
        if n % i == 0:
            cnt += 1
    cnt += 1 # n 본인 추가
    return cnt

def solution(number, limit, power):
    answer = 0
    for i in range(1, number+1):
        atk = count_divisor(i)
        if atk > limit:
            atk = power
        answer += atk
    
    return answer

하지만 이 문제는 이 방법도 runtime을 초과하게 설계해놨다.

약수에는 반드시 짝이 있다 : 1부터 n**(1/2)까지 계산

약수를 다시 살펴보자
6의 약수는 [1, 2, 3, 6]. 1*6 = 6이고 2*3=6이다.
이처럼 약수는 언제나 곱했을 때 n이 되도록 해주는 짝이 있다.
단 한 경우를 제외하고.
9의 약수 [1, 3, 9]처럼, 동일한 수를 제곱하여 n이 되는 경우.

그렇다면, 약수를 셀 때 어떠한 i가 n의 약수인 순간, 1개가 아니라 2개를 세버리는 방법이 있다.
이렇게 한 번에 짝을 세어준다면, for문의 연산을 1부터 n의 제곱근까지로 크게 축소시킬 수 있다.
단, 제곱근이 정수인 경우에는 1번만 세어주면 되고.
(이 방법의 코드는 아래에서)

코드

최종적으로는 runtime이 가장 짧은 아래 코드만 통과할 수 있었다.

def count_divisor(n):
    cnt = 0
    for i in range(1, int(n**(1/2))+1):
        # i가 n의 약수라면
        if n % i == 0:
            cnt += 1
            # i가 n의 제곱근이라면 cnt를 더하지 않는다
            if i**2 != n:
                cnt += 1
    return cnt

def solution(number, limit, power):
    answer = 0
    for i in range(1, number+1):
        atk = count_divisor(i)
        if atk > limit:
            atk = power
        answer += atk
    
    return answer

알게된 점

약수의 개수만 구해도 되는 문제의 경우, 약수의 성질을 통해서 연산량을 크게 줄일 수 있었다.

그리고 알고리즘 문제의 경우, 단순히 코드가 돌아간다뿐 아니라 얼마나 효율적인지를 고민하는 것도 중요한 포인트라는 점을 생각하게 되었다.
아직 코드가 돌아가는 지 여부에만 집중하고 있었는데, SQL도 그렇고 알고리즘도 그렇고,
(1) 사람이 볼 때 얼마나 직관적으로 이해가 잘 되는지
(2) 그렇다면 그 코드가 얼마나 효율적인지
이 2가지 포인트를 잡아가며 고민하고 진행 해야겠다.