[백준] 1072-게임(C++)

문제링크:https://www.acmicpc.net/problem/1072

1072번: 게임

 

 

일반 반복탐색은 1000000000번 탐색을 반복해야하기 때문에 무조건 시간초과(대략 10초)

킹반적인 이분탐색문제입니다.

 

이분탐색 개념이 모호하시다면, 아래 링크를 참고하세요! 

https://cjh5414.github.io/binary-search/

이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제

 

접근방식

 

1. 일반적인 반복은 시초니까 이분탐색을 사용해보자

 

 

문제풀이 

 

1. result 를 -1로 저장한다. 만약 불가능하다면 result 값을 갱신하지 않아서 -1이 그대로 남게 된다.

 

2. 일반적인 이분탐색 방식으로 구현 코드를 보면 이해가 더 빠를듯

 

정답 코드입니다.

#include <iostream>
#include <cmath>
using namespace std;

double x, y;
double z;
int result = -1;


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> x >> y;
	z = (y * 100) / x;
	z = floor(z);

	int low = 1;
	int high = 1000000000;

	while (low <= high) {
		int mid = (low + high) / 2; // 범위 ㄱㅊ
		double val = (double)((y + mid) * 100) / (x + mid);
		val = floor(val);
		if (val > z) {
			result = mid;
			high = mid - 1;
		}
		if (val <= z) {
			low = mid + 1;
		}
	}


	cout << result << endl;

	return 0;
}