프로그래머스 [연습문제 / 기사단원의 무기](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 기사단원의 무기

---

문제 링크: 문제 보기

문제 설명:

각 기사단원은 자신의 번호에 해당하는 수의 약수 개수만큼 공격력을 갖는 무기를 지급받습니다. 단, 약수의 개수가 limit보다 크면 power로 대체 지급됩니다. 모든 기사단원의 무기 공격력 합을 구하는 문제입니다.

---

문제 해결 코드

#include <string>
#include <vector>

using namespace std;

int solution(int number, int limit, int power) {
    int answer = 0;

    for (int i = 1; i <= number; i++) {
        int cnt = 0;

        // 약수 개수 구하기 (제곱근까지 탐색)
        for (int j = 1; j * j <= i; j++) {
            if (i % j == 0) {
                cnt += 2; // 짝인 경우 두 개의 약수
                if (j * j == i) cnt -= 1; // 제곱수는 중복 제거
            }
        }

        // 조건에 따라 무기 공격력 누적
        answer += (cnt > limit) ? power : cnt;
    }

    return answer;
}

---

코드 설명

• 핵심 알고리즘: 각 수의 약수 개수를 구한 뒤, limit을 초과하면 power로 대체하는 조건 분기 처리
• 구현 세부사항:
• 약수는 대칭적으로 존재하므로, 1부터 √i까지 탐색하며 약수 개수를 계산
• i가 제곱수인 경우 중복된 약수를 한 번만 센다 (j * j == i)
• cnt가 limit 초과일 경우 power로 처리
• 시간 복잡도 분석:
• 각 수마다 약수 계산: O(√n)
• 전체 계산: O(n√n)
• number의 최대 값이 크지 않으므로 충분히 효율적

---

결과

이 코드는 기사 번호별 약수 개수를 효율적으로 계산하여 무기 공격력을 합산합니다. 조건에 맞는 대체 처리를 통해 정확한 공격력 합계를 반환합니다.

추가 최적화로는 약수 개수를 미리 배열에 캐싱해두거나, 동적 프로그래밍을 통해 반복 계산을 줄일 수 있습니다.