[백준] 1977번 : 완전제곱수 (C언어 / C99)

문제

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

 

 

조건 및 입출력

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

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

 

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	int start, end;
	scanf("%d %d", &start, &end);

	int sum = -1; //합계 구하기
	int first = 0;

	for (start; start <= end; start++)
	{
		if (sum == -1)
			first = start; // sum이 바뀌면 최초 제곱수 발견했다는 뜻.

		for (int i = 1; i <= 100; i++)// 종료지점: 최댓값 10000의 루트배
		{
			if (start == i * i)
			{
				sum += i * i;
				break;
			}
		}
	}

	if (sum != -1)
	{
		printf("%d\n", sum + 1); // 완전제곱수가 있는 경우
		printf("%d\n", first);
	}
		
	else
		printf("%d\n", sum); //완전제곱수가 없는 경우

	return 0;
}

 

 

 

풀이 과정

제곱수를 찾는 최댓값은 10000이다. 그럼 1부터 100까지 제곱을 했을 때, M과 N사이의 어느 한 값이랑 일치하면 그 수는 완전제곱수를 의미한다.

 

초기 sum의 값은 -1로 설정했다. 완전제곱수가 없는 경우 -1을 출력해야 하기 때문이다. 

만약, 완전제곱수가 있는 경우 완전제곱수의 합인 sum에 + 1 로 보정을 해주면 된다.

 

루프를 start(문제에선 M)에서 end(문제에선 N)까지 돌린다.

그후 루프를 1부터 100까지 돌린다. (이중루프)

 

만약 start값이 1부터 100까지 제곱을 했을 때 일치하는 수라면, sum에 누적가산을 해 준다.

또한, sum의 값이 바뀌었다는 것은 최초의 완전제곱수가 나와서 더해졌음을 의미함으로 바뀌기 직전의 i*i의 값이 최초의 완전제곱수이다.

 

그 후 루프 연산이 끝나면, 결과를 출력한다.

만약 sum에 더해진 것이 없다면(=완전제곱수가 없다면) -1이 있을 것이며, 그대로 sum을 출력한다.

sum이 -1이 아니라면 완전제곱수가 적어도 하나 이상있다는 얘기이므로 sum+1을 해 준 결과를 출력한다. (초기 sum의 값이 -1이므로)

sum이 바뀌기 전의 값은 first 변수에 저장되어 있으므로 first 변수의 값을 출력한다.

 

 

---

여담

 

파이썬으로 풀었다면 금방 했을 것 같은데, C로 풀려고 보니까 뭔가 생각할 게 많다보니 문제를 푸는 데 오래 걸린다.

 

요즘 토익 공부한다고 블로그 글 올리는게 뜸하다. (백준은 매일마다 하고 있긴 하다만,,,)

매일 적어도 하나씩은 올려야겠다.

 

코드가 이상하거나, 이해되지 않는 부분이 있다면 언제든 댓글 남겨주세요! + 더 좋은 풀이 방법이 있다면 알려주시면 감사하겠습니다 :)