코딩/백준 문제 (브론즈)
[백준/1977/C언어] 완전제곱수 풀이
룻밤
2023. 7. 13. 18:31


https://www.acmicpc.net/problem/1977
1977번: 완전제곱수
M과 N이 주어질 때 M이상 N이하의 자연수 중 완전제곱수인 것을 모두 골라 그 합을 구하고 그 중 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 완
www.acmicpc.net
반복문을 이용한 풀이
#include <stdio.h>
int main() {
int m, n; // 입력값 m, n
int x = 1; // 나누는 수
int sum = 0, min = 10000; // 완전제곱수 합, 완전제곱수 최솟값
scanf("%d %d", &m, &n);
for (int i = m; i <= n; i++) { // i는 m부터 n값까지
for (int j = x; j <= i; j++) { // x나누는 수는 최댓값이 i 이하
if (i / j == j && i % j == 0) { // 나누는 수와 몫이 일치함 + 그랬을때 나머지가 0 = 완전제곱수
sum += i; // 완전제곱수일때 덧셈
if (min > i) // i값이 가장 작을때 min
min = i;
}
}
}
if (sum == 0) // 완전제곱수가 없을때
printf("-1");
else { // 있을때
printf("%d\n", sum);
printf("%d\n", min);
}
return 0;
}
배열을 이용한 풀이
#include <stdio.h>
int main() {
int m,n;
int sum=0, min=10000;
int a[10000];
scanf("%d %d",&m,&n);
for(int i=0; i<=n; i++) {
a[i]=i*i;
if(m<=a[i]&&a[i]<=n){
sum+=a[i];
if(min>a[i])
min=a[i];
}
}
if(sum==0)
printf("-1");
else
printf("%d\n", sum);
printf("%d\n", min);
return 0;
}
처리시간으로 봤을때 배열을 이용한 풀이가 더 낫다고 할 수 있겠다.