[백준/C++] 1484번: 다이어트

문제

풀이

현재 몸무게^2 - 이전 몸무게^2 = G를 만족하는 현재 몸무게를 찾는 문제이다.

H^2 - L^2 <= G면 H++

H^2 - L^2 > G면 L++ 을 반복하면서

H^2 - L^2 > G이면서 H - L == 1 이면 종료한다.

몸무게의 범위가 주어져있지 않아서 당황스러웠는데 인접한 제곱수끼리의 차가 G보다 크면 더 이상 답이 나올 수 없어서 종료하면 된다.

또한 두 포인터의 시작을 1로 설정해야한다. 그렇지 않으면 2^2 - 0^2 같은 답이 나오게 된다.

 

코드

#include <iostream>
#include <queue>
using namespace std;

int G;
priority_queue<int, vector<int>, greater<int>> answer;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> G;

	for (int low = 1, high = 1; ;) {
		if (high * high - low * low > G && high - low == 1) break;
		if (high * high - low * low == G) answer.push(high);
		if (high * high - low * low > G) low++;
		else high++;
	}

	if (answer.empty()) cout << -1;

	while (!answer.empty()) {
		cout << answer.top() << '\n';
		answer.pop();
	}
	
	return 0;
}