(C++) - 백준(BOJ) 1484번 : 다이어트

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

1484번: 다이어트

이분탐색 문제입니다.

📕 풀이방법

📔 입력 및 초기화

 1. g를 선언, 하나도 답을 찾지 못했을 때를 알기 위한 bool 변수 flag, 제곱수들을 저장할 vector형 변수 square를 선언합니다.

 

 2. g를 입력 후 10만까지의 제곱수를 square에 저장합니다.

 

*10만 * 10만은 100억이므로 int범위를 초과합니다. 수는 long long형으로 저장해줍니다.

📔 풀이과정

 1. 현재 몸무게를 w라고 생각했을 때 이전 몸무게는 w * w - g가 됩니다. 이 w를 1 ~ 10만까지 loop를 돌며 답이 있는지 찾습니다.

 

 2. 이전 몸무게는 저장된 제곱수들이 있는 square에 대해 이분탐색을 시행합니다. key는 w * w - g로 하여 수행합니다. w * w - g와 같은 값이 square안에 있다면 정답을 찾았으므로 

w를 출력해주며 답이 최소 한 개이상 있으므로 flag = true로 설정합니다.

 

📔 정답출력

 flag = false면 -1를 출력합니다. 아니라면 2번에서 정답을 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll g;
bool flag;
vector <ll> square;
int main(){
    cin >> g;
    for(ll i = 1; i <= 100000; i++) square.push_back(i * i);
    for(ll w = 1; w <= 100000; w++){
        auto x = lower_bound(square.begin(), square.end(), w * w - g);
        if(*x == w * w - g){
            flag = true;
            cout << w << '\n';
        }
    }
    if(flag == false) cout << -1;
}