기사단원의 무기

알파로그·2023년 3월 12일
0

✏️ 문제 설명

숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다.

기사들은 무기점에서 무기를 구매하려고 합니다.

각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다.

단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고,

제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.

예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로,

공격력이 4인 무기를 구매합니다.

만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고

제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면,

15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무기를 구매합니다.

무기를 만들 때, 무기의 공격력 1당 1kg의 철이 필요합니다.

그래서 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 합니다.

기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 power가 주어졌을 때,

무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 return 하는 solution 함수를 완성하시오.

✏️ 제한 사항

  • 1 ≤ number ≤ 100,000
  • 2 ≤ limit ≤ 100
  • 1 ≤ power ≤ limit

✏️ 문제 풀이

📍 첫번째 풀이 (실패 : 시간초과 - 11,12,14,15,16,24,25)

시간초과가 될거라고 생각을 못해서 효율성을 코드에 반영하지 못했다.

코드 자체에 문제는 없는것같으니 효율성을 좋게 수정해봐야겠다.

int number = 10;
        int limit = 3;
        int power = 2;

        int answer = 0;

        //---------------------------------------//

				// 약수의 갯수를 담는 배열
        int[] aliquot = new int[number];

				// i = 배열의 index 번호	
        for (int i = 0; i < number; i++) {

						// j = i의 약수를 구하기위해 나눠지는 숫자
            for (int j = 1; i + 1 >= j ; j++) {

								// 나누어 떨어질 경우 index 에 1을 추가하고
                aliquot[i] += ((i + 1) % j == 0) ? 1 : 0;

								// limit 보다 index 가 클 경우 값을 power 로 변경
                if (aliquot[i] > limit){
                    aliquot[i] = power;
                    break;
                }
            }
        }
        for(int i : aliquot)
            answer += i;

        System.out.println(answer);

📍 두번째 풀이 (성공)

for 문으로 인수를 구할 때

예를들어 number = 5 라면 첫번째 for 문 1에서 나머지가 0 이되므로 1은 인자가 맞다.

이때 나눈값인 5도 인자가 맞지만 이전 코드에서는 루프를 끝까지 돌아 5가 입력될때까지 불필요한 컴파일이 진행됬다.

문제는 어느지점에서 루프를 멈춰야하는것인가 인데 구글링 도중 제곱근의 숫자만큼만 루프를 돌리면 된다는것을 알게되어 코드를 작성해봤다.

int number = 10;
        int limit = 3;
        int power = 2;

        int answer = 0;

        //---------------------------------------//

				
        int[] aliquot = new int[number];

        for (int i = 0; i < number; i++) {
						// 제곱근을 구하는 변수 (i가 0부터 시작하기때문에 +1 을 더해줌)
            int sqrt = (int) Math.sqrt(i + 1);

						// j가 제곱근 값과 같은 경우를 누락할경우
						// 인수의 갯수가 홀수 거나 인수의 차이가 1인경우가 누락이된다.
            for (int j = 1 ; j <= sqrt ; j++){

								// number 가 j로 떨어질경우 인자의 작은 값이 구해짐 (+1)
                if ((i+1) % j == 0){
                    aliquot[i] ++;

								// 이때 number 를 j 로 나누면 인자의 큰 값이 구해짐 (+1)
								// 만약 j로 나눈 값이 j라면 인자의 작은값과 큰값이 동일하다는 뜻이다.
								// 앞의 if 문에서 인자가 추가되었기 때문에 이 경우는 값을 추가하지않는다.
                    if ((i+1) / j != j)
                        aliquot[i] ++;
                }

								// 이렇게 구해진 인자값이 limit 를 넘어갈 경우 power 로 값을 변환해준다.
                if (aliquot[i] > limit){
                    aliquot[i] = power;
                    break;
                }
            }
        }
        for(int i : aliquot)
            answer += i;
        System.out.println(answer);

🔍 코드 리뷰

Q.

어째서 제곱근 까지만 loop를 돌리면 인자의 딱 중간값까지 값을 구할 수 있게되는것인가?

A. 🔗 Q. 참고

제곱근에 소숫점을 제거해준후 제곱을 하면 제곱을 했을때 원래숫자보다 같거나 적은 가장 가까운숫자가 나오게된다.

이 뜻은 제곱근보다 더 큰 수로 loop 를 돌릴 때 부터 큰수의 인수값이 구해진다는 뜻이다.

🔗 문제 원본 : 기사단원의 무기

profile
잘못된 내용 PR 환영

0개의 댓글