백준 1484 (다이어트)

알고리즘: 투포인터

 

G의 범위가 100,000이기 때문에 N^2 - (N - 1)^2 >= 100,000인 N의 범위까지 조사하면 된다.

위를 만족하는 N은 50,000.

front, last를 이용해서 투포인터 알고리즘을 사용하여 구현

1) diff가 G보다 크다면 front를 증가, 

2) diff가 G라면 출력값 벡터에 push.

3) diff가 G보다 작다면 last를 증가.

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
int main(void){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int G;
    cin >> G;
    int front = sqrt(G) + 1, last = 1;
    vector<int> vec;
    while(1) {
        int origin = front * front;
        int thinking = last * last;
        int diff = origin - thinking;
        if(front == 50001 && last == 50000) break;
        if(diff == G){
            vec.push_back(front);
            if(front != 50001) front++;
        } else if(diff < G) {   
            if(front != 50001) front++;
            else if(front == 50001) break;
        } else last++;
    }

    if(vec.size()) {
        for(int i = 0; i < vec.size(); i++)
            cout << vec[i] << "\n";
    } else cout << "-1\n";
    return 0;
}