[프로그래머스] C# : 약수의 합

프로그래머스 코딩테스트 연습 Level 1 - 약수의 합

코딩테스트 연습 - 약수의 합

문제의 핵심

1. 약수를 찾는 효율적인 방식을 알고 있는가?

 

---

약수의 뜻은 나머지가 없이 나눠 떨어지는 값을 의미한다.

 

n의 약수는,

n을 나눴을 때 나머지가 발생하지 않는 숫자들을 뜻한다.

ex) 10의 약수 : 1, 2, 5, 10

 

 

1부터 시작해서 자기자신 또한 약수임을 주의해야한다.

가장 간단한 방법은 n이 입력되면, for문을 n번 돌려서 하나하나 약수를 찾으면 된다.

 

 

but,

약수의 특징을 파악한다면  for문의 반복을 절반 줄일 수 있다.

n의 약수 중 자기자신을 제외하고 가장 큰 약수는 n/2 이하의 값이다.

 

---

n이 짝수라면 n/2가 두번째로 큰 약수이고

ex) 10의 약수 : 1 2 5 10 중 두번째는 5이고, 5 = 10/2

 

n이 홀수라면, 두번째로 큰 약수는 n/2보다는 작다.

ex) 9의 약수 : 1, 3, 9 중 두번째는 3이고, 3 < 9/2

---

 

따라서 for문을 n/2번만큼 돌려주고

마지막에 n을 더해주면 모든 약수의 합을

가장 적은 계산으로 얻을 수 있다.

 

 

 

정답 코드

public class Solution
    {
        public int solution(int n)
        {
            int answer = 0;
            
            // i가 1부터 n/2값이 될때까지 증가시키면서 for문 반복
            for (int i = 1; i <= n/2; i++)
            {
                if (n % i == 0)
                {
                // 나눠떨어지면 약수이므로 곧장 answer에 더해줌
                    answer += i;
                }
            }
            // 마지막으로 자기자신 n을 더해주면서 리턴한다.
            return answer + n;
        }
    }