백준 1484: 다이어트

문제 요약

G킬로그램은 성원이의 현재 몸무게의 제곱에서 성원이가 기억하고 있던 몸무게의 제곱을 뺀 것이다.

성원이의 현재 몸무게로 가능한 것을 모두 출력하는 프로그램을 작성하시오.

문제 분류

• 수학
• 두 포인터

문제 풀이

현재 몸무게인 j와 기억하고 있던 몸무게인 i를 활용하여 두 포인터로 탐색하는 문제이다.
j의 제곱인 jj와 i의 제곱인 ii에 대해 jj - ii가 g보다 작다면 j를 1증가시키고, jj - ii가 g보다 크다면 i를 1증가시킨다.

이런식으로 반복하면서 jj - ii가 g와 같은 것에 대해 j를 출력하면 된다.

bool타입의 d로 성공 여부를 저장하여서, 해당 j가 없는 경우에는 -1을 출력하도록 해주었다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int g;
	long long i, j, ii, jj;
	bool d = false;
	cin >> g;
	for (i = 1, j = 2; i < j;) {
		ii = i * i;
		jj = j * j;
		if (jj - ii < g)
			j++;
		else if (jj - ii > g)
			i++;
		else {
			d = true;
			printf("%d\n", j++);
		}
	}
	if (!d) printf("-1");
	return 0;
}