[Java][프로그래머스][Level 1] 약수의 합

문제 설명

자연수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요.

 

제한 사항

• n은 0 이상 3000이하인 자연수입니다.

생각

간단하게만 생각하면 너무 간단한 문제이다. for문을 사용하여 자연수 n을 n보다 작은 자연수로 나눠 나누어 떨어지면 answer에 더해주면 되기 때문이다. 하지만 그럼에도 내가 글을 작성한 이유는 거기서 한번 더 생각을 해보자고 생각했기 때문이다. 36의 약수를 생각해보자. 1 2 3 4 6 9 12 28 36 이다. 6을 기준으로 대칭을 이루는 수들을 곱해주면 36이 나온다! 이를 이용해서 문제를 풀기로 하였다. n-1까지의 자연수로 나누는 것이 아닌 n의 제곱근까지 나누는 것이다. 그러고 나온 수들을 대칭을 이용해서 문제를 풀기로 하였다.

 

코드

class Solution {
      public int solution(int n) {
          int answer = 0;
          
          for(int i=1; i<=n/2; i++) {
              if(n%i==0) {
                  //i로 나누떨어지면 i와 대칭되는 수인 n/i도 더해준다.              
                  answer += i;
                  answer += n/i;
                  
                  //제곱근이 약수인 경우는 2번 더해지므로 한번을 빼준다.
                  if(i==n/2) {
                      answer -= i;
                  }
              }
          }
          
          return answer;
      }
    }

문제 자체는 간단하지만 좀 더 연산횟수를 줄이는 생각을 항상 해야한다!