[백준/C++] #1484 다이어트 (Two Pointer)

문제

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

 

 

 

구상

두 제곱수의 차가 G가 되는 경우를 출력하는 문제였다. 

제곱수로 이루어진 배열 만들고, 투 포인터로 두 수 찾아서 출력하면 되는 간단한 문제였다. 

 

풀이 + 코드

G는 100,000보다 작거나 같은 수이기에 두 제곱수의 차가 100,000보다 큰 최대한 작은 제곱수를 구해보면 대략 51,000 이 나온다. (51,000^2 - 50,999^2 = 101,999)
제곱수로 이루어진 배열 (1^2 ~ 51000^2) 만들고 투 포인터 이용해서 제곱수의 차 구하면 된다. 

int형의 크기는 4 byte / -2,147,483,648 ~ 2,147,483,647 인데, 
51000^2는 2,601,000,000로 int 범위를 넘어섰다. -> long long 사용하자

#include<iostream>
#include<vector>
#define MAX 51000
#define INF 987654321
#define endl "\n"
using namespace std;
/*
1484번 다이어트
*/

int G; // 증량 KG 100000보다 작다
vector<long long> arr(MAX, 0);

void makeArr() {
    arr[0] = 0;
    for (int i = 1; i < MAX; i++) {
        arr[i] = (long long)i * i;
    }
}

void solution() {
    makeArr();
    bool flag = 0;

    // two pointer
    int s = 1; int e = 1;
    while (e < MAX) {
        long long diff = arr[e] - arr[s];
        if (diff == G) { // 찾앗다면
            cout << e << endl; // 출력하고
            flag = true;
            e++; 
        }
        else if (diff < G) { // 작다면 키우고
            e++;
        }
        else { // 크다면 줄이고
            s++;
        }

        if (s == e) { // 순서 뒤바뀌지 않도록 -> 사실 없어도 됨..
            e++;
        }
    }

    if (!flag) {
        cout << -1 << endl;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> G;

    // 로직
    solution();

    return 0;

}