백준 1484번 - 다이어트

www.acmicpc.net/problem/1484

1484번: 다이어트

이분 탐색으로 쉽게 해결할 수 있었던 문제이다.

 

문제 태그에는 수학, 투 포인터가 적혀 있는데 나는 문제를 보고 이분 탐색으로 충분히 풀릴 것 같아서 제출해봤는데..

 

틀렸습니다..

 

잉? 하고 문제를 다시 보니 가능한 몸무게가 없을 때 -1을 출력하는 것을 까먹어버렸다ㅎㅎ

 

저 조건을 다시 붙여서 바로 제출하니 맞았습니다를 받을 수 있었다.

 

 

풀이 과정

 

일단 G의 값이 100000 보다 작은 자연수라는 조건이 가장 큰 힌트였다.

 

G = (현재 몸무게)^2 - (기억하고 있던 몸무게)^2이다.

이때 G가 자연수라는 조건이 있기 때문에 반드시 현재 몸무게가 기억하고 있던 몸무게보다 커야 한다는 것을 쉽게 찾아낼 수 있다.

 

그렇다면 위의 조건을 통해 또 얻어낼 수 있는 것은 현재 몸무게의 최댓값이다.

 

현재 몸무게를 x라고 해보자. 

그럼 위에서 구한 조건들에 따라 어떠한 경우에도 x^2 - (x-1)^2이 10만보다 작아야 한다.

 

(x-1을 기억하고 있던 몸무게로 정한 이유는 몸무게의 최댓값을 얻기 위함이다.

계산된 G의 최솟값이 10만이 넘지 않는 그러한 G들 중 최댓값을 구하는 과정인 것이다.) 

 

식을 풀어써보면

음.. 중학생도 풀 수 있는 식이니까 생략하고 x가 약 50000보다 작거나 같아야 한다는 것을 알 수 있다.

 

그럼 실제로 그런지 확인해보자.

 

sqrt(50000) - sqrt(49999) = 99999이고

sqrt(50001) - sqrt(50000) = 100001이다.

 

정확히 5만까지만 x를 구해도 모든 경우를 확인해 볼 수 있었다.

 

따라서 x를 1~5만까지 각각 이분 탐색을 돌린다고 생각해 봤을 때 

시간 복잡도 = O(5만 log(5만))이기 때문에.. 충분!!

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
    int g;
    cin >> g;
    vector<int>ans;
    for (int i = 1; i <= 50000; i++) {
        int left = 1, right = i;
        while (left <= right) {
            int mid = (left + right) / 2;
            int temp = (i * i) - (mid * mid);
            if (temp == g) {
                ans.push_back(i);
                break;
            }
            else if (temp > g) left = mid + 1;
            else right = mid - 1;
        }
    }
    if (ans.size() == 0) cout << "-1" << "\n";
    else {
        for (int i = 0; i < ans.size(); i++) {
            cout << ans[i] << "\n";
        }
    }
}