BOJ 1977 완전제곱수

완전제곱수

시간 제한 메모리 제한
2초 128MB

문제

M과 N이 주어질 때 M이상 N이하의 자연수 중 완전제곱수인 것을 모두 골라
그 합을 구하고 그 중 최솟값을 찾는 프로그램을 작성하시오.
예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 완전제곱수는
64, 81, 100 이렇게 총 3개가 있으므로 그 합은 245가 되고 이 중 최솟값은 64가 된다.

입력

첫째 줄에 M이, 둘째 줄에 N이 주어진다.
M과 N은 10000이하의 자연수이며 M은 N보다 같거나 작다.

출력

M이상 N이하의 자연수 중 완전제곱수인 것을 모두 찾아
첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.
단, M이상 N이하의 자연수 중 완전제곱수가 없을 경우는 첫째 줄에 -1을 출력한다.

예제 입력

60
100

예제 출력

245
64

풀이

Python의 내장 함수들을 적절하게 잘 이용하면
Pythonic하면서 간단하게 구현할 수 있다.

완전제곱수란

문제를 해결하기 전에 우선 완전 제곱수에 대하여 간단히 설명하겠다.
완전 제곱수정의는 정수의 제곱으로 된 수로
예를 들어 42의 제곱이므로 완전제곱수
25의 경우 5의 제곱이므로 완전제곱수다.
예제의 경우 60에서 100사이의 완전제곱수
64(8 X 8), 81(9 X 9) 100(10 X 10) 세 가지다.

조건의 판단

해당의 수가 완전제곱수인지 판단하기 위해서는
해당 수의 제곱근정수면 해당 수는 완전제곱수다.

Pythonic하게 구현하기

  • 🌟🌟🌟 List Comprehension 🌟🌟🌟
    List Comprehension이 무엇인지는 여기를 참고하는 것이 좋을 것 같다.
  • lambda 함수 사용
    lambda(익명 함수)가 무엇인지는 여기을 참고하는 것이 좋을 것 같다.
  • 3항 연산자 사용
    Python에서 3항 연산자는 a if condition else b 형식이다.
    a가 조건이 True일 때 실행되는 문장
    b가 조건이 False일 때 실행되는 문장이다.
  • 내장 함수 사용

    • list()
      Sequence Type을 리스트로 반환하는 함수
    • filter(func, iterable)
      반복 가능 자료형에서 func함수의 값이 True인 것만 묶어서 반환
    • is_integer()
      해당 값이 정수이면 True를 반환하는 함수
    • sqrt()
      math 모듈의 제곱근을 반환하는 함수

등등.. 더 많은 함수들을 사용하긴 했지만 모를만한 함수는 이정도 인 것 같다.

알고리즘

  1. N부터 M사이의 list를 생성한다.
  2. 리스트의 모든 수의 제곱근정수인지 판단한다.
  3. 2번의 조건이 True인 값만으로 새로운 리스트생성한다.
  4. 리스트의 길이가 0인 경우는 완전제곱수가 없는 경우(-1출력)
  5. 아닌 경우 sum함수와 min함수를 사용하여 합과 최소값 출력

유의할 점

sum함수와 min함수는 str형을 반환하지 않기 때문에
문제의 조건과 같이 출력하기 위하여 str함수를 사용해 해당 값들을
str형으로 변환하고 값의 출력에 개행(\n)이 존재하기 때문에
str(sum) + "\n" + str(min)의 형식으로 출력해준다.

코드 구현부

Pythonic Code

from math import sqrt

perf_squ_num = list(filter(lambda x: sqrt(x).is_integer(),
                           [i for i in range(int(input()), int(input()) + 1)]))

print(-1) if len(perf_squ_num) == 0 else print(str(sum(perf_squ_num)) \
                                               + "\n" + str(min(perf_squ_num)))

Readable Code

from math import sqrt

M = int(input())
N = int(input())

perf_squ_num = []

for i in range(M, N+1):
    if sqrt(i).is_integer():
        perf_squ_num.append(i)

if len(perf_squ_num) == 0:
    print(-1)

else:
    print(sum(perf_squ_num))
    print(min(perf_squ_num))

결과

2 3

숏코딩 53위!!

숏코딩에 욕심은 없지만 Readable한 코드로 처음에 작성하였다가
짧고 Pythonic하게 구현할 수 있을 것 같아 코드를 줄여보았다.
개인적으로는 나쁘지 않게 구현한 것 같다.
Pythonic한 코드와 Readable한 코드 둘 중에 무엇이 정답인지는 판단할 수 없다.
둘 다 알맞은 코드라고 생각한다. 개인적으로는 Pythonic코드가 더 좋다.

✅ 코드는 [여기]에서 확인할 수 있다.


Written by@Minsu Kim
Software Engineer at KakaoPay Corp.