[백준 / BOJ] 17374 비트베리

문제

출처 : https://www.acmicpc.net/problem/17374

17374번: 비트베리

페카즈는 자신이 갖고있는 비트코인의 수를 최대로 하고싶다. 

페카즈와 빈센트가 할 수 있는 거래가 주어질때, 최대 비트코인수를 구하는 문제다.

 

---

풀이

이분탐색으로 푼 문제다.

 

할수있는 거래그래프는 아래와 같은데, 아래를 보면 베리를 코인으로 최대로 바꾸는것이 항상 최선임을 알수있다.

비트 -> 코인

코인 -> 비트

베리 -> 코인

코인 -> 베리

베리 -> 코인 -> 비트

 

얻을 수 있는 비트코인을 최대로 하려면, 비트와 코인중 더 작은값을 최대로 해야한다.

비트는 처음에 주어지므로, 코인을 구하는 식에 집중해서 문제를 풀었다.

코인을 구하는 식은 아래와 같이 세울수있다. 

A개의 bit를 주었을때, B개의 coin을 얻을수있다고 하자. 이때, coin의 갯수는 다음과 같이 구할 수 있다.

 

coin = (bit/A) * B;

 

이때, 위의 bit값을 적절히 조절하며 coin의 값을 구하면된다.

 

이때, 모든 경우를 다 봐주면 시간초과가 나기때문에, 이분탐색을 통해 봐줬다.

 

우리가 원하는값은 |bit - coin|의 최솟값이다. 따라서, 그래프 형태는 1차원 그래프가 아닌, 볼록 그래프형태가 되는데, 이를 이분탐색으로 풀기위해서, "|bit-coin|은 최소로 하되, coin의 갯수는 bit의 갯수보다 항상 작다." 라는 제약을 추가해 이분탐색후, 반복문을 통해서 위아래로 +A -A를 해줘 답을 찾아줬다.

(위 제약을 추가하기싫다면 삼분탐색으로 풀면됨)

 

 

주요 소스코드

		private long getMaximumBit(){
			long left = -1*this.coin, right = this.bit;
			while(left < right){
				long mid = (left + right) / 2;
				if(operCoin(mid) > operBit(mid)) right = mid-1;
				else left = mid+1;
			}
			return Math.max(left, right);
		}

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/17374%20%EB%B9%84%ED%8A%B8%EB%B2%A0%EB%A6%AC/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃