코딩/백준 문제 (브론즈)

[백준/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;
}

처리시간으로 봤을때 배열을 이용한 풀이가 더 낫다고 할 수 있겠다.