[프로그래머스] 기사단원의 무기

🔗알고리즘 문제

프로그래머스의 문제는 대부분 로직자체는 떠올리기 쉽지만 시간초과로 인해 고생하는 문제들이 많은 것 같다. 평소 코드 최적화를 잘 하지 못한다고 생각했는데, 종종 프로그래머스도 풀며 연습해보아야겠다!

문제 분석

이 문제는 기사의 수, 공격력 제한, 제한수치 초과 시 공격력 을 인수로 받아서 모든 기사의 무기를 만드는데에 철괴 몇개가 사용되는지 알아내는 문제이다.

기사는 1번 부터 기사의 수 번 까지 번호를 할당받고 각 번호의 약수의 갯수로 공격력이 정해진다.

이 때 기사의 공격력이 공격력 제한을 초과한다면 해당 기사의 공격력은 제한수치 초과 시 공격력으로 치환된다.

기사의 무기를 만드는데에는 기사의 공격력1당 철괴 하나가 사용된다.

knight number = 5, limit = 3, limit power = 2

-----

1 | 1
2 | 1, 2
3 | 1, 3
4 | 1, 2, 4
5 | 1, 5

필요한 철괴 = 1 + 2 + 2 + 3 + 2 = 10

발상 & 알고리즘 설계

간단하게 소인수 분해를 이용하여 약수의 갯수를 구해주고 계산하는 방식을 사용했지만 시간초과가 떠서 좀 더 효율적인 소인수 분해 알고리즘에 대해 생각해보았다.

먼저 일반적인 약수 구하기의 로직은 이와 같다.

for(int i = 1; i <= n; i++){
    if(n % i == 0) answer++;
}

하지만 생각해보면 3의 약수 1, 3 처럼 n의 약수가 i이면 다른 약수는 n / i 가 된다.
그렇다면 굳이 약수를 구할 때 n의 끝까지 for문을 돌리지 않아도 된다는 얘기다.

for(int i = 1; i * i <= n; i++){
    if(i * i == n) answer++;
    else if(n % i == 0) answer += 2;
}

이런식으로 로직을 교체하게 되면 시간복잡도 또한 O(√n)으로 방법 1보다 빨라지게 된다.

코드

#include<iostream>

using namespace std;

int solution(int number, int limit, int power);

int main(){
    int number;
    int limit;
    int power;

    cin >> number >> limit >> power;

    cout << solution(number, limit, power);
}

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

    for(int i = 1; i <= number; i++){
        for(int j = 1; j * j <= i; j++){
            if(j * j == i) divisor++;
            else if(i % j == 0) divisor += 2;
        }

        if(divisor > limit) value += power;
        else value += divisor;

        divisor = 0;
    }

    return value;
}