[200511] 약수의 합 - 연습문제(level1)

1. 문제이해

- 정수 n의 약수들의 합 구하기

 

2. 전략

- n의 제곱근일때까지 약수 쌍을 찾으면 answer에 더해주기

1) n%i == 0일때
2) i == Math.sqrt(n)이면 i를 아니면 i + n/i를 더해주기

 

3. 참고사항

- Math.sqrt(n)까지 돌리면 for문의 실행 횟수를 훨씬 줄일 수 있다!!

--> 시간 복잡도를 줄이는 방법 항상 고민하기!!

 

4. 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i = 1; i <= Math.sqrt(n); i++){
            if(n%i == 0)
                answer += (i == Math.sqrt(n)) ? i : i + n/i;
        }
        return answer;
    }
}