[백준 1484번] 다이어트

문제 링크: https://www.acmicpc.net/problem/1484

1484번: 다이어트

<문제 풀이> 투 포인터

G = E^2 - S^2를 만족하는 E를 구하면 된다.

 

E = 1, S = 1 에서 시작

다음을 반복한다.

 

1. E^2 - S^2 > G 이면서 E - S가 1이면 반복문 종료(가장 인접한 제곱수 끼리의 차가 G보다 크면 더 이상 답을 구할 수 없다 -> 1, 4, 9, 16,.... 나열해보면 알 수 있음)

2. E^2- - S^2 > G 이면 S++

3. E^2- - S^2 <= G 이면 E++

 

<c++ 소스 코드>

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int g;
    cin >> g;
    long long e = 1, s = 1;
    bool existed = false;
    while (true) {
        if (e * e - s * s == g) {
            existed = true;
            cout << e << "\n";
        }
        if (e - s == 1 && e * e - s * s > g) break;
        if (e * e - s * s > g) s++;
        else e++;
    }
    if (!existed) cout << -1;
    
    return 0;
}