BOJ #5710. 전기 요금 (Gold 하위권)

지난번에 제가 개인적으로 운영하는 그룹에서 모의대회 연습에 있었던 문제입니다.

바로, 백준 5710번. 전기 요금 문제입니다.

www.acmicpc.net/problem/5710

5710번: 전기 요금

H번으로 있었는데, 이 때 저는 저 문항을 시간초과를 받고 틀렸었죠.

오늘 낮에 다시 풀어봤는데 맞왜틀하길래 뭔가 했는데, 함수 계산식을 하나 잘못 썼었습니다...

이 문제 자체가, 로직은 맞더라도 실수로 틀리기 쉬운 문제인 듯 합니다.

---

의식의 흐름.

처음에 봤을 땐 수학, 구현인 듯한 느낌이 들었습니다.

그리고 역시나, 제 예상은 들어맞더군요. 이 문항으로 시간 꽤나 잡아먹었습니다.

문제 이해하는 데에도 꽤나 시간이 들었죠.

A가 합친 이용량의 요금, B는 요금의 절댓값 차여서 어려웠던 문제입니다.

차라리 A가 이용량의 합이었으면 좋았을텐데 말이죠. (근데 이러면 H번이 아니고 B번 정도이지 않았을까요ㅋㅋㅋ....)

 

다행히 두 명의 전기 사용량의 합이 무조건 10억 미만이고, 절댓값 차도 10억 이하이기 때문에 int형 범위는 넘어가지 않아 typedef long long ll 설정은 필요하지 않습니다.

---

해결 방법.

먼저, A를 이용하여 두 명이 이용한 전기사용량을 구해줍니다. 이 부분은 단순 구현입니다. 빡구현도 아니고, 10~15분 정도 투자하면 됩니다.

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

A는 전기요금, acount는 전기 사용량입니다.

이렇게 하면, 두 명의 전기 사용량 합은 구할 수 있겠죠.

스펠링이 조금 이상하지만 넘어갑시다. 아무튼, 주의할 점은 acount에 더해줄 때, min(A, 200)으로 하지 않고 단순 A으로 하면 안된다는 점입니다.

 

이제 두 명의 전기 사용량 합을 구했으니, 상근이가 아예 사용하지 않았을 때부터, 상근이가 혼자 독차지했을 때까지 비교해보면서 정답일 때를 찾아야 합니다.

---

시간초과가 뜨지 않을까요?

---

아니요. 물론 저처럼 for문으로 다 돌아서 확인하면 O(N)의 시간복잡도로, 확인하는 데에만 1초는 족히 넘어가 시간초과를 받게 됩니다. 따라서 여기서 바로 이분탐색을 활용하는 겁니다.

 

일단, lower_bound풀이는... 떠오르지 않네요ㅋㅋㅋㅋㅋ

아쉽네요. 결국 이분탐색을 구현해야 합니다.

 

상근이가 0W를 사용했을 때부터(low), 혼자 독차지할 때까지(high)로 범위를 주어 이분탐색하게 했습니다.

이 때, 사용량에 따른 요금 계산 함수를 또 만들어주었습니다. 위 함수를 거꾸로 만들어주면 되겠네요.

int p(int A) {
	int acount = 0;
	acount += min(A, 100) * 2;
	A -= 100;
	if (A > 0) {
		acount += min(A, 9900) * 3;
		A -= 9900;
		if (A > 0) {
			acount += min(A, 990000) * 5;
			A -= 990000;
			if (A > 0) {
				acount += A * 7;
			}
		}
	}
	return acount;
}

 A는 전기 사용량, acount는 전기 사용량에 따른 요금입니다.

그리고, 상근이가 0W를 사용했을 때부터(low), 혼자 독차지할 때까지(high)로 범위를 주어 이분탐색하게 했습니다. (위에 했던 말 또하게 됐네요)

	int sum = e(A);
		int lo=0, hi=sum;
		while(lo<=hi){
			int mid=(lo+hi)/2;
			M=mid;
			N=sum-M;
			int ans1=p(M);
			int ans2=p(N);
			if(ans2-ans1==B){
				cout<<ans1<<"\n";
				break;
			}
			if(ans2-ans1>B)
			    lo=mid+1;
			else
			    hi=mid-1;
		}

저는 이분탐색 코드를 짤 때 무조건 lo<=hi , lo=mid+1, hi=mid-1 조건을 지킵니다. (변수명은 조금 달라질 수 있습니다.)

이분탐색 코드는 범위체크에 따라 답이 확 달라질 수 있기 때문에 헷갈리지 않기 위해서 저만의 코드 규칙을 정해놓았습니다.

---

주의사항 및 반례.

아래 예제를 돌렸을 때 아래와 같이 나와야 합니다.

Input
1100 300	// 예제
35515 27615	// 예제
1100 800	
100000000 0	// 시간초과가 나오는가?
4979977 4979968	// 1W, 1000010W. 함수를 100만W 이상까지 제대로 짰는가?
0 0

Ans:
350
2900
120
48989950
2

---

소스 코드.

#include <iostream>
#include <algorithm>
using namespace std;
int A, B, M, N;
int e(int A) {
	int acount = 0;
	acount += min(A, 200) / 2;
	A -= 200;
	if (A > 0) {
		acount += min(A, 29700) / 3;
		A -= 29700;
		if (A > 0) {
			acount += min(A, 4950000) / 5;
			A -= 990000 * 5;
			if (A > 0) {
				acount += A / 7;
			}
		}
	}
	return acount;
}
int p(int A) {
	int acount = 0;
	acount += min(A, 100) * 2;
	A -= 100;
	if (A > 0) {
		acount += min(A, 9900) * 3;
		A -= 9900;
		if (A > 0) {
			acount += min(A, 990000) * 5;
			A -= 990000;
			if (A > 0) {
				acount += A * 7;
			}
		}
	}
	return acount;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	while (cin >> A >> B) {
		if (!A && !B)
			break;
		int sum = e(A);
		int lo=0, hi=sum;
		while(lo<=hi){
			int mid=(lo+hi)/2;
			M=mid;
			N=sum-M;
			int ans1=p(M);
			int ans2=p(N);
			if(ans2-ans1==B){
				cout<<ans1<<"\n";
				break;
			}
			if(ans2-ans1>B)
			    lo=mid+1;
			else
			    hi=mid-1;
		}
	}
}

 

수학과 이분탐색, 구현을 이용해야 하는 문제였습니다.

개인적으론 Silver II ~ Gold V 정도의 문제라 생각이 듭니다.

 

조언 및 피드백은 언제나 환영입니다.