2026/07/23 코드카타

 

[문제] 기사단원의 무기

https://school.programmers.co.kr/learn/courses/30/lessons/136798

 

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int solution(int number, int limit, int power) {
    int answer = 0;
    
    int divisor = 0;
    int final_power  = 0;
    int power_sum = 0;
    for (int i = 1; i <= number; ++i)
    {
        // 대원 한 명씩 약수 개수 구하기
        for (int j = 1; j <= i; ++j)
        {
            if (i % j == 0)
            {
                ++divisor;
            }
        }
        
        if (divisor > limit)
        {
            final_power = power;
        }else
        {
            final_power = divisor;
        }
       
        power_sum += final_power;
        divisor = 0;
    }
   
    answer = power_sum;
    
   return answer;
    
}

 

[풀이 과정]

약수를 구하면서 완전 탐색 방식으로 for loop으로 1~기사 숫자까지 모두 순회하면서 약수인지 아닌지 판단

-> 각 기사의 약수 개수를 divisor 변수에 저장

-> 해당 기사의 divisor가 다 구해지면, limit을 초과하는지 아닌지 판단해서 최종 공격력을 power_sum에 저장함

-> 모든 기사의 무기 공격력이 다 합쳐지면 그게 정답.

 

[개선점 탐구]

약수를 완전탐색이 아닌 다른 방식으로 찾을 수 있을 것 같다.

-> 약수를 구할 때는, 원래 숫자의 제곱근까지만 찾으면 된다. 

15의 약수를 구한다고 생각했을 때, 3으로 나눠서 5로 나누어떨어진다. 이 경우 5도 15의 약수이기 때문에 약수 두 개를 동시에 구할 수 있다. 원래 숫자의 제곱근 X 제곱근이 중간에 존재할 것이기 때문에, 제곱근을 기준으로 양쪽의 약수들을 한번에 구할 수 있다.

예시) 16: 1 * 16, 2 * 8, 4 * 4, 8 * 2, 16 * 1

제곱근을 기준으로 양쪽에 같은 약수들이므로 굳이 4 * 4 이후까지 안 가도 된다는 뜻.