[C언어 기출문제&풀이] 완전 제곱수

프로그램 명: square

제한시간: 1 초

M 과 N 이 주어질 때 M 이상 N 이하의 자연수 중 완전제곱수인 것을 모두 골라 그 합을 구하고 그 중 최소값을 찾는 프로그램을 작성하시오.

완전 제곱수란 어떤 자연수를 제곱해서 만들수 있는 수이다. 1*1 , 2*2 , 3*3 , 4*4 , 5*5 , ....

예를 들어 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

출처: koi 고등부 지역본선 1 번

풀이 : 앞에서 풀었던 거듭제곱 문제를 활용하여 푼다. 

소스코드 : 
01
#include <stdio.h> 
02
  
03
int main() 
04
{ 
05
    int m,n,i,j,ar[100],p=0,sum=0,min; 
06
    scanf("%d %d",&m,&n); 
07
    for(i=m;i<=n;i++) 
08
    { 
09
    for(j=0;j<=i;j++) 
10
    { 
11
        if(j*j==i) 
12
        { 
13
        ar[p]=i; 
14
        p++; 
15
        } 
16
    } 
17
    } 
18
    min=ar[0]; 
19
    for(i=0;i<p;i++) 
20
    { 
21
    sum=sum+ar[i]; 
22
        if(ar[i]<min) 
23
        min=ar[i]; 
24
    } 
25
    if(p==0) 
26
    printf("-1\n"); 
27
    else
28
        printf("%d\n%d",sum,min); 
29
}