[Algorithm]Baekjoon 1484번 :: 다이어트

https://www.acmicpc.net/problem/1484

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
 
int g;
vector<long long> v;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> g;
 
    for (long long i = 0; i <= g; ++i)
    {
        v.push_back(i * i);
    }
 
    int start = 1;
    int end = 2;
    vector<long long> answers;
 
    while (start + end <= g)
    {
        if (v[end] - v[start] > g)
        {
            ++start;
        }
        else if (v[end] - v[start] < g)
        {
            ++end;
        }
        else
        {
            answers.push_back(end);
            ++start;
        }
    }
 
    if (answers.size() == 0)
    {
        cout << -1;
    }
    else
    {
        for (int i = 0; i < answers.size(); ++i)
        {
            printf("%lld\n", answers[i]);
        }
    }
}
 
 

 

투포인터의 반복횟수는 최대 몇인가? 에 대해 고민했던 문제.

챗지피티덕분에 이해할 수 있었다.

코드에서 알 수 있다시피, s + e <= g이다.

 

즉, 현재무게 + 이전무게는 반드시 g이하이다.

이해 한방에 되는 예시는 아래와 같다.

 

 

 

 

현재무게 ^ 2 - 이전무게 ^ 2 = G 이다.

즉, (현재무게 + 이전무게) * (현재무게 - 이전무게) = G로 다시 고칠 수 있다.

 

근데 현재무게든, 이전무게든 두 수는 1이상의 자연수이고, 반드시 현재무게가 이전무게보다 더  크다. (G값은 1이상이기 때문에 같을 수 없다)

 

그렇다면 '현재무게 - 이전무게'는 1보다 더 낮아질 수 없다. 

그러니 결국 최대횟수를 결정하는것은 '현재무게 + 이전무게' 이다. 두 수를 곱했을 때, 한쪽 수가 1이니 나머지 수의 최대값은 결국 G값이랑 동일할 수 밖에 없다. 

여기서 나머지 수란 X+Y이니, 최대횟수는 X+Y <= G가 되는것이다.