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

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

 

문제를 이해하기 힘들었다. 기억하고 있는 몸무게라니 이게 무슨말인지,, 그런데 질문게시판을 참고하고 문제를 몇번 다시 읽어보니 

기억하고 있는 몸무게 = 이전 몸무게 였다.

 

1. beforeWeight + G = afterWeight

2. afterWeight^2 - beforeWeight^2 = G

 

이 두 식으로 푸는 수학 문제라 생각했는데 여기서 G는 단순 차이가 아니라 새롭게 정의되어 있는 것이었다. 그러니까 1번 식은 잘못되었다.

 

afterWeight는 a, beforeWeight 는 b라 할 때, 2번을 식을보면 G는 반드시 0보다 큰 자연수이기 때문에 a는 반드시 b보다 크다.

 

그리고 두 수를 선택해서 비교하는 작업은 두포인터가 가장 적합하다.

 

a^2 - b^2 = value 라 할 때

 

만약 value > G 이면 현재 차이가 너무 큰 것이므로 b를 +1 하여 차이를 줄여준다. 이렇게 비교하며 만약 value = G 이면 답을 출력하고 a, b 모두 +1 한다.

 

또한 만약 a = b 가 되는 순간이 온다면 이것은 더이상 답에 가깝게 갈 수 없다는 의미이므로 탐색을 종료한다.

 

약간의 수학과 두포인터를 연습할 수 있었던 좋은 문제였다.

 

#include <iostream>
#define ll long long
using namespace std;

int main(){
    ll N; cin >> N;

    ll a = 2;
    ll b = 1;

    bool flag = true;

    while(a > b){
        ll tmp = a * a - b * b;

        if(tmp == N){
            cout << a << '\n';

            a++;
            b++;

            flag = false;
        }else if(tmp < N){
            a++;
        }else if(tmp > N){
            b++;
        }  
    }

    if(flag) cout << -1 << '\n';
}