Skip to main content

[Java] 136798 기사단원의 무기

📝 기사단원의 무기

1. 문제 요약

  • 기사 번호는 1번부터 number까지 존재함.
  • 각 기사는 자신의 번호의 약수 개수만큼의 공격력을 가진 무기를 구매함.
  • 예: 15번 기사 → 약수(1, 3, 5, 15) → 공격력 4
  • 하지만, 공격력이 limit을 초과하면 power 값으로 고정됨.
  • 예: limit=3, power=2
  • 공격력 4 > limit(3) → 무기 공격력 2로 구매
  • 무기 제작 시 공격력 1당 철 1kg 필요
  • 즉, 모든 기사들의 최종 공격력을 합산한 값이 필요한 철의 무게

2. 정답코드

class Solution {
    public int solution(int number, int limit, int power) {
        // 번호의 약수 개수에 해당하는 공격력
        // 단, 제한 수치 limit 넘어가면 power 구매
        // limit = 공격력일 때는 limit 구매 가능
        // 공격력 1당 철 1kg 
        // 모든 무기 만들기 위해 필요한 철의 무게 리턴
        
        int answer = 0;
        
        for (int i = 1; i <= number; i++) {
            int paladinNum = i; // 기사 번호 
            int attackCnt = divisorCnt(i);
            if (attackCnt > limit) {
                answer += power;
            } else {
                answer += attackCnt;
            }
        }
        
        return answer;
    }
    
    public int divisorCnt(int n) { // pladinNum의 공격력 약수 계산하는 메서드
        int attack = 0;
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                attack++;
                if (i != n / i) attack++;
            }
        }
        
        return attack;    
    }
}
  • for문 (1 ~ number) 으로 각 기사를 한 명씩 순회하면서 약수계산 메서드 divisorCnt(i) 호출→ 기사 번호 i의 약수 개수 = 공격력
  • 공격력 > limit 크면 power 적용, 아니면 원래 공격력 더함
  • 최종 철의 무게 answer에 누적해서 반환

3. 오답 / 어려웠던 점

공격력 약수 계산에서 시간초과가 난 이유는 시간복잡도 O(n)이라서

public int divisorCnt(int n) { // pladinNum의 공격력 약수 계산하는 메서드
    int attack = 0;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            attack++;
        }
    }
    
    return attack;    
}

image.png

  • 약수구할때 √n까지만 확인하면 된다 약수는 항상 짝을 이루기 때문이다
  • 작은 쪽 약수만 찾으면 큰 쪽은 자동으로 알 수 있다.
  • 그래서 √n까지만 돌리면 모든 약수를 찾을 수 있다.
  • i * i ≤ n
  • if (i != n / i) attack++;

1. 내가 푼거 (O(n))

public int divisorCnt(int n) {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) cnt++;
    }
    return cnt;
}

모든 수를 다 나눠보는 방식

2. 효율적인 방법 (O(√n))

public int divisorCnt(int n) {
    int cnt = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            cnt++;                // 작은 약수
            if (i != n / i) cnt++; // 짝꿍 약수 (제곱수 중복 방지)
        }
    }
    return cnt;
}

예를 들어 n=12라면

  • i=1 → (1,12) → +2
  • i=2 → (2,6) → +2
  • i=3 → (3,4) → +2
  • i=4부터는 i*i > n이므로 종료
  • 최종 cnt = 6 (약수는 1,2,3,4,6,12)

제곱수일 때 약수가 중복돼서 두 번 세지 않으려고 아래 코드 씀

if (i != n / i) attack++;

반례

예를 들어 n = 36일 때 i = 6

  • n % 6 == 0이니까 6은 약수 → attack++
  • 그런데 짝꿍 약수는 n / i = 36 / 6 = 6 → 자기 자신
  • 즉, 이미 attack++ 했는데 또 attack++ 하면 6을 두 번 세는 꼴

그래서 if (i != n / i)를 붙여서 짝꿍이 자기 자신이 아닐 때만카운트하도록 추가하는 조건이다.



Back to top