[프로그래머스] [C#] 약수의 개수와 덧셈

안녕하세요.

오늘은 프로그래머스 코딩테스트 연습 문제인 "약수의 개수와 덧셈" 을 풀어 보았습니다.

 

문제 링크

---

https://programmers.co.kr/learn/courses/30/lessons/77884

코딩테스트 연습 - 약수의 개수와 덧셈

 

 

문제 풀이 방법

---

해당 문제의 관건은 약수의 개수가 홀수인지, 짝수인지 구하는 것 입니다.

그래서 보통 이 문제를 해결하기 위해 약수의 개수를 구해도 되지만 저는 조금 다르게 문제를 해석하였습니다.

 

약수의 개수가 홀수가 되려면 n의 제곱근이 정수여야 한다는 것입니다.

약수는 a x b의 쌍으로 이루어지는데 제곱근의 경우 a x a를 이루기 때문에 자연스럽게 홀수가 되는 것이죠.

16의 경우

(1 x 16)

(2 x 8)

(4 x 4)

로 5개의 약수를 가지게 되는 것이죠.

 

이러한 방법을 사용하여 저는 문제를 풀었고,

이번 문제는 평균 약 0.29ms 정도의 속도로 테스트를 통과하였습니다.

 

코드

---

using System;

public class Solution {
    public int solution(int left, int right) {
        int answer = 0;
        for(int i=left; i<=right; i++) {
            if(Math.Pow((int)Math.Sqrt(i), 2) == i) {
                answer -= i;
            } else {
                answer += i;
            }
        }
        return answer;
    }
}