[백준 1484번] 다이어트 (C++)

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int G;

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> G;
    int s=1, e=2;

    bool check = false;
    while(s<e)
    {
        int tmp = e*e-s*s;
        if(tmp == G)
        {
            cout << e << "\n";
            check = true;
        }

        if(tmp<=G) e++;
        else s++;
    }

    if(!check) cout << -1;

    return 0;
}

 

일반 브루트포스로는 오래 걸리기에 투 포인터로 풀이가 가능한 문제이다.

우리가 구하는 G는 쉽게 e*e-s*s임을 알 수 있다.

따라서 해당 값을 계산한 tmp의 값이 목표 G보다 작거나 같다면 e 값을 올려 값 격차를 올려 다음 값 탐색을 이어나간다.

아니라면 s 값을 올려 값의 격차를 좁혀 목표 G를 찾아나간다.

추가로 찾지 못한 경우에 대비하여 예외처리 또한 해주어야 한다.