[코드포스/개별문제] CF#623 B번 Homecoming

클릭하면 코드포스 페이지로 이동합니다.

---

코드포스 #623 B번 - Homecoming

집에 가기 위한 길이 있다. 길은 걸어가거나, 버스 또는 전차를 타고 이동할 수 있다. 입력으로 교차로의 상태가 주어지는데, A는 버스로, B는 전차로 이동할 수 있는 길이고, 버스와 전차는 서로 갈아탈 수 있다. 각각의 티켓은 가격을 지불해야 하고, 현재 가지고 있는 돈이 주어진다. Petya가 현재 가진 돈으로 집으로 돌아가기 위해 걸어가야 하는 최소 거리를 구하시오.

간단한 이분탐색 문제이다. 걸어가서 처음 탑승하는 정류장의 위치를 이분탐색을 통해 검색한다.

각각의 탐색에서 집으로 가기위한 티켓의 총 비용을 계산한다.

만약 돈이 부족하다면 더 많이 걸어가야 하고,

돈이 충분하다면, 최소 거리가 있을 수 있으므로 더 가까운 거리에서 탐색한다.

 

아래는 제출코드이다.

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))

// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};

// 전역변수

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int tc;
	cin >> tc;

	while(tc--) {
		int a, b, p;
		cin >> a >> b >> p;
		string s;
		cin >> s;
		ll ans = s.size();

		int le = 0, ri = s.size() - 1;
		while(le <= ri) {
			// 탑승하는 정류장의 위치
			int mid = (le + ri) / 2;
			// 이번 시행에서 사용하는 돈의 총액
			ll curpay = 0;
			// 현재 타고있는 이동수단
			char state = s[mid];

			if(state == 'A') {
				curpay = a;
			} else {
				curpay = b;
			}

			for(int i = mid + 1; i < s.size() - 1; i++) {
				if(state != s[i]) {
					// 갈아타야 함.
					state = s[i];
					if(state == 'A') {
						curpay += a;
					} else {
						curpay += b;
					}
				}
			}

			if(p < curpay) {
				le = mid + 1;
			} else {
				ans = min((ll)(mid + 1), ans);
				ri = mid - 1;
			}
		}

		cout << ans << "\n";
	}
	
	return 0;
}