Lv1_[기사단원의 무기, C++] 알고리즘 정리 - 프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

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

프로그래머스

---

이번 문제의 핵심은 약수를 구하는 것이다.

왜냐하면 기사의 number의 약수가 본인의 공격력이 때문에 약수를 구하는 것이 필수!

 

약수를 구하는 방법이 기억이 잘 안나서 검색해보니 초등학교 5학년..에 배웠던거였음..

 

https://workingdog.tistory.com/51

약수 구하기 [수학]

 

위의 약수 구하기를 보고 오시면 됩니다.

 

프로그래밍으로 약수 구하는 방식은

1) 나머지 연산(%) 시 결과 값이 0일 때 (몫이 정수로 나누어 떨어지는 수)
2) (num*num)을 초과한 값으로 나누지 않기 (나누는 값이 몫을 초과하기 전까지 나눔)
(※ 제곱근으로 푸는 방법이 있고, sqrt()루트 값으로 푸는 방법이 있다. 결과는 같으므로 편한 방식으로 풀면 됩니다)
3) (나누는값, 몫)이 모두 약수니까 약수 값 +2, 하지만 "나누는값==몫"이면 중복이므로 약수 값 +1

위의 방법으로 number마다 약수의 개수를 뽑을 수 있습니다.

 

또한 문제에서 (기사의 공격력 > 공격력 제한수치)가 되면 기사의 공격력을 공격력 제한수치로 변경해주면 된다.

위와 같은 조건을 생각해서 풀면 다음과 같은 코드가 나옵니다.

 

#include <string>
#include <vector>
 
using namespace std;
 
int solution(int number, int limit, int power) {
    int answer = 0;
 
    for(int num = 1; num <= number; num++) {
        // number별 약수 개수 구하기
        int count = 0;
        for(int i = 1; (i*i) <= num; i++) {
            if(num % i == 0) {
                int share = (int)(num / i);
                if((share*share) == num) {
                    count += 1;
                } else {
                    count += 2;
                }
            }
        }
 
        // 약수 개수가 limit 넘는지 비교
        if(count > limit) {
            answer += power;
        } else {
            answer += count;
        }
    }
    
    return answer;
}

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓