[백준] 1977 - 완전제곱수



문제 정보


  • 문제 이름: 완전제곱수
  • 문제 번호: 1977
  • 문제 유형: 알고리즘 - 수학
  • 풀이 언어: C
  • 제출 시간: 2019년 5월 11일 20시 28분 29초
  • 원본 링크: https://www.acmicpc.net/problem/1977



문제

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



입력

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



출력

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



결과 - 소스코드 및 랭크






메모

이 문제를 보고 처음에는 소수 문제를 풀듯이 하나씩 줄여나가면서 나눠보면 되겠거니 생각했었는데 그렇게 하면 너무 많은 경우를 연산하게 돼서 다른 방식을 생각해보게 되었다.

고민해보니 해당 범위 내의 숫자에 루트를 씌워 자연수로 딱 떨어지는지 확인해보면 될 것 같아서 먼저 sqrt(i)에서 정수로 형변환 시킨 sqrt(i)를 뺐을 때 0이 나오는지 체크하였다.

만약 완전제곱수가 아니라면 소수점 아래 숫자가 생길 것이기 때문에 그 부분만 확인하면서 문제를 해결할 수 있었다.

[백준] 1977 - 완전제곱수

https://y8ncastle.world/2019/05/11/boj/1977-c/

Author

Alec J

Posted on

2019-05-11

Updated on

2021-02-09

Licensed under