백준 1484번, 다이어트 풀이

문제

BOJ 1484

풀이

문제에서 주어진 조건대로 식을 세워봅시다.

성원이가 기억하고 있는 몸무게를 $ M $, 현재 몸무게를 $ x $로 둡시다.

 

$$ x^2 - M^2 = G $$

$$ (x - M)(x + M) = G $$

 

 

$ a = x - M, b = x + M $이라고 둡시다. (단, $ a $, $b $는 정수)

$ a \cdot b $이 $ G $가 되려면, $ a $와 $ b $가 $ G $의 약수가 되면 됩니다.

 

$ a $와 $ b $를 알고 있으니 연립 일차 방정식을 사용하여 $ x $를 구할 수 있습니다.

$$ x = \frac{a + b}{2} $$

자연수라는 조건을 충족하려면, $ a + b $가 짝수가 되면 됩니다.

 

 

엣지 케이스를 생각해봅시다.

약수 $ a $와 $ b $가 같은 경우, 즉 $ G $의 제곱근이 되는 경우 $ x $ 또는 $ M $이 0이 되므로 이 경우를 제외해야합니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int G; cin >> G;
	set<int> s;
	for (int a = 1; a < sqrt(G); a++) {
		if (G % a) continue;
		int b = G / a;
		if ((a + b) % 2) continue;
		s.insert((a + b) / 2);
	}

	if (s.empty()) cout << "-1";
	else for (auto it = s.begin(); it != s.end(); it++) cout << *it << "\n";
}