👓 문제 설명
성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. 성원이는 엔토피아가 선물해준 저울 위에 올라갔다. “안돼!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! G 킬로그램이나 더 쪘어ㅜㅠ”라고 성원이가 말했다. 여기서 말하는 G킬로그램은 성원이의 현재 몸무게의 제곱에서 성원이가 기억하고 있던 몸무게의 제곱을 뺀 것이다.
성원이의 현재 몸무게로 가능한 것을 모두 출력하는 프로그램을 작성하시오.
💣 제한 사항
- 첫째 줄에 G가 주어진다. G는 100,000보다 작거나 같은 자연수이다.
- 첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다.
- 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우는 제외해야 한다.
🚨 접근 방법
(현재 몸무게)^2 - (과거 몸무게)^2 = g, 의 경우를 찾는 문제이다.
몸무게는 양수이므로 1부터 가질 수 있다.
g가 최대 10만이므로, a^2 - b^2 = 99999일 때,
a는 최대 50000까지 가능하다.
(50000^2 - 49999^2 = 99999)
따라서 int 범위에서 변수 선언을 해도 무방하다.
현재, 과거 몸무게를 1부터 시작해서
두 수의 제곱의 차가 g와 같거나, 미만, 초과 3가지 경우로 나눈다. (if, else if가 아닌 if, if, else 이어야한다.)
-> else if로 할 경우 현재 몸무게가 같을 때, 정답 벡터에 추가한 후 다음 경우의 수 탐색을 하지 않아 무한 루프에 걸리게된다.
따라서, 정답 벡터에 추가한 경우 과거 몸무게를 +1하여 새로운 몸무게에 대해 탐색을 진행한다.
- if 차이 == g : 정답 벡터에 현재 몸무게 추가
- if 차이 < g : 현재 몸무게 +1
- else 차이 > g : 과거 몸무게 +1
🚈 풀이
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int g;
void func() {
// cur의 제곱 - prev의 제곱 <= 10만
// 50000 제곱 - 49999 제곱 = 99999
// 최대 50000까지 확인하면 된다.
vector<int>ans;
int prev = 1, cur = 1;
while (cur<g) {
int dif = cur * cur - prev * prev;
if (dif == g)ans.push_back(cur);
if (dif < g)cur++;
else prev++;
}
if (ans.empty())cout << -1;
else {
for (auto p : ans)cout << p << "\n";
}
}
int main() {
cin >> g;
func();
return 0;
}