[백준][이분 탐색] 1484 다이어트 c++구현

목차

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

1484번: 다이어트

문제

 

문제 풀이 시 주의할 점

현재 몸무게와 그 전 몸무게가 자연수인 것을 주의 해야 한다.

처음에 식을 풀어서 이분 탐색을 했는데 식을 풀지말고 A^2-B^2 형태로 이분탐색을 해야한다.

 

 

 

문제 풀이

내가 탐색하고자 하는 현재몸무게를 A, 그 전 몸무게를 B라고 놓으면 G = A^2-B^2의 형태가 나온다.

그 후 A를 기준으로 B를 이분탐색해주면 된다.

 

 

 

코드구현

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
vector<int> v;
int main() {
	int G;
	cin >> G;
	int i, j, start = 1, mid, end = G;  
	for (i = 1; i <= G; i++) {
		start = 1;
		end = G;
		while (start <= end) { //이분 탐색 시작
			mid = (start + end) / 2;
		
			if (pow(i, 2) - pow(mid, 2) > G) {  
				start = mid + 1;

			}
			else if (pow(i, 2) - pow(mid, 2) < G) {
				end = mid - 1; 
			}
			else {
				v.push_back(i);
				break;
			}
		}
		
	}
	if (v.empty()) {  //비어있으면 -1출력
		cout << -1;
		return 0;
	}
	sort(v.begin(), v.end());  //정렬
	for (auto iter = v.begin(); iter < v.end(); iter++) {
		cout << *iter << "\n";
	}

	//A^2-B^2 = G => A를 구해야함(A, B는 자연수 주의)
}