약수의 개수와 덧셈-파이썬(Python) [프로그래머스/코딩테스트 연습/Lv.1]

문제

https://school.programmers.co.kr/learn/courses/30/lessons/77884?language=python3

프로그래머스

 

문제 설명

 

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ left ≤ right ≤ 1,000

입출력 예

left	right	result
13	17	43
24	27	52

입출력 예 설명

입출력 예 #1

• 다음 표는 13부터 17까지의 수들의 약수를 모두 나타낸 것입니다.

수	약수	약수의 개수
13	1, 13	2
14	1, 2, 7, 14	4
15	1, 3, 5, 15	4
16	1, 2, 4, 8, 16	5
17	1, 17	2

• 따라서, 13 + 14 + 15 - 16 + 17 = 43을 return 해야 합니다.

입출력 예 #2

• 다음 표는 24부터 27까지의 수들의 약수를 모두 나타낸 것입니다.

수	약수	약수의 개수
24	1, 2, 3, 4, 6, 8, 12, 24	8
25	1, 5, 25	3
26	1, 2, 13, 26	4
27	1, 3, 9, 27	4

• 따라서, 24 - 25 + 26 + 27 = 52를 return 해야 합니다.

---

풀이

def solution(left, right):
    answer = 0
    for i in range(left,right+1):
        sqrt_i=int(i**0.5)
        if sqrt_i**2==i:
            answer-=i
        else:
            answer+=i
    return answer

---

설명

사실 이 문제는 수학적인 지식을 알고 있다면 간단하게 풀 수 있다. 그 지식이란 "완전 제곱수의 약수의 개수는 홀수이다." 이다. (*왜 그런지는 구글에 검색해보자...)

 

answer라는 변수를 만들어 0으로 초기화하고, for문을 통해 i를 left부터 right까지로 하여 i가 완전 제곱수일 경우 answer에서 빼주고 아닐 경우 더해준다. 완전 제곱수인지 판별하는 방법은 다음과 같다. i를 0.5 제곱한 값에 int()로 정수로 변환한 값을 sqrt_i 값에 대입해준다. 그리고 sqrt_i를 제곱한 값이 i와 같을 경우 i는 완전 제곱수인 것이다. (자세한 내용은 아래 "Tip" 참고)

이후 answer를 반환한다.

 

Tip (아래 "더보기" 클릭)

어떤 정수가 완전 제곱수인지 판단하는 방법은 이 문제에도 나온 적이 있다.

https://20mini.tistory.com/9?category=1102532 

[프로그래머스/코딩테스트 연습/Lv.1] 정수 제곱근 판별-파이썬(Python)

어떤 정수 n이 완전제곱수 였으면 n의 제곱근은 정수이므로 int()함수를 해도 값이 그대로일 것이고, 그 값을 제곱한 수는 n과 같을 것이다. 그러나 n이 완전제곱수가 아니었으면 n의 제곱근은 소수점 아래의 값을 가지고 있을 것이고, n의 제곱근에 int()함수를 실행한 값은 n의 제곱근에서 소수점 아래의 값을 버린 값이 된다. 따라서 그 값을 제곱한 수는 n과 다를 것이다.

---

TIL

없음