Skip to main content

250831


3문제

  • 기사단원의 무기 ok
  • 2016년
  • 과일장수


기사단원의 무기

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 <= n; i++) {
            for (int j = 1; j <= i; j++) {
                if (i % j == 0) {
                    attack++;
                }
            }
        }

        return attack;
    }
}

image.png

틀린이유 - 이중포문

divisorCnt 메서드에서 이중포문 씀.
main에서 for문 쓰고 있으니까 divisorCnt는 하나의 숫자 n에 대해서 약수 몇 개 인지 구하기만 하면 됨

수정한 코드 

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 <= 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)

수정한 코드

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;    
    }
}

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

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)를 붙여서 짝꿍이 자기 자신이 아닐 때만카운트하도록 추가하는 조건이다




과일장수

class Solution {
    public int solution(int k, int m, int[] score) {
        // 사고ㅏ몇 박스 ? score.length / m;
        // 각 사과 점수 계산 
        int len = score.length; // 사과박스 
        int box = len / m; // 점수 길이 
        int answer = 0; // 최대이익
        
        // 사과점수 내림차순
        // int[] → Integerp[]로
        Integer[] arr = Arrays.stream(score).boxed().toArray(Integer[]::new);
        Arrays.sort(arr, Collections.reverseOrder());
        
        
        for (int i = 0; i < len; i++) {
            
            // 길이를 m으로 나눠서 카운트 ㅓ장하고, 초기화
            // 사과 점수 계싼 공식 Math.min(사과1, 사과2, 사과3, 사과4...) * m
            // 여기 어떻게 처리>?
        }
        
        return answer;
    }
}





Back to top