[백준 5710][이분탐색][C++] 전기 요금

 

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

5710번: 전기 요금

구현과 이분탐색을 적절히 섞어놓은 문제였습니다.

 

아이디어로는 상근이가 아예 전기를 안쓴 경우(0 Wh)부터 전기를 전부 썼을 경우(A Wh) 사이를 이분탐색으로 구하는 것입니다. 이분탐색의 규칙으로는, 중앙값을 상근이가 사용한 전기의 양, 총사용량에서 중앙값을 뺀 값이 이웃이 사용한 전기의 양이고 이웃-상근이의 값이 B이면 이때의 상근이의 전기요금을 반환, 아니면 이분탐색을 하도록 하였습니다.

 

따라서, 요금을 받고 전기사용량을 반환해주는 함수와 전기사용량을 받고 요금을 반환해주는 함수가 필요했습니다. 구현 자체는 매우 간단하니 쉽게 구현할 수 있습니다.

 

이분탐색로 풀 수 있음은 금방 깨달았으나, 규칙을 설정하는데에 잘못 생각해서 푸는데 오래걸린 케이스의 문제였습니다. 

// 전체코드
#include<iostream>
#include<algorithm>
using namespace std;

int a,b,awh;

int get_price(int wh){
	if(wh<100){
		return wh*2;
	}
	else if(wh<10000){
		return 200+(wh-100)*3;
	}
	else if(wh<1000000){
		return 29900+(wh-10000)*5;
	}
	else{
		return 4979900+(wh-1000000)*7;
	}
}

int get_wh(int price){
	int wh=0;
	wh+=min(price,200)/2;
	price-=200;
	if(price>0){
		wh+=min(price,29700)/3;
		price-=29700;
		if(price>0){
			wh+=min(price,4950000)/5;
			price-=990000*5;
			if(price>0){
				wh+=price/7;
			}
		}
	}
	return wh;
}

int bsearch(int l, int r){
	int mid = (l+r)/2;
	int sg = get_price(mid);
	int neigh = get_price(awh-mid);
	
	if(neigh-sg==b){
		return sg;
	}
	if(l==r){
		return 0;
	}
	if(neigh-sg>b){
		return bsearch(mid+1,r);
	}
	else{
		return bsearch(l,mid-1);
	}
}

int main(){
	while(1){
		cin>>a>>b;
		if(a==b && a==0){
			return 0;
		}
		awh = get_wh(a);
		cout<<bsearch(0,awh)<<endl;
	}
}