백준 10510 Bricks

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

벽돌을 떼어낼 수 있다면 왼쪽에서부터 떼어내면 됩니다. 벽돌 하나의 비율은 전체 벽돌의 비율과 같기 때문에, 왼쪽에서부터 벽돌을 떼어낼 시점을 알아낼 수 있습니다. 왼쪽에서부터 벽돌 뭉치들이 들어온다고 생각하겠습니다.

검은색 벽돌 뭉치가 들어왔다고 가정합시다. 떼어내지지 않고 남은 벽돌 들+들어온 검은색 벽돌 뭉치의 일부의 비율이 전체 벽돌의 비율과 같아진 순간 벽돌을 떼어내고 남은 검은색 벽돌을 남겨두는 식의 그리디로 풀면 됩니다. 하얀색도 마찬가지입니다.

코드를 보겠습니다.

#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
deque<pii> v;
ll gcd(ll a, ll b){
	return a%b>0?gcd(b,a%b):b;
}
int brick(ll b, ll w){
	int ans=0;
	ll cb=0,cw=0;
	while(!v.empty()){
		pii vf=v.front(); v.pop_front();
		if(vf.ff=='B'){
			if(cw>0 && cw%w==0LL){
				if(cb+vf.ss>=(cw/w)*b && (cw/w)*b>cb){
					ans++;
					ll rm=cb+vf.ss-(cw/w)*b;
					cb=rm,cw=0;
				}
				else cb+=vf.ss;
			}
			else cb+=vf.ss;
		}
		else{
			if(cb>0 && cb%b==0LL){
				if(cw+vf.ss>=(cb/b)*w && (cb/b)*w>cw){
					ans++;
					ll rm=cw+vf.ss-(cb/b)*w;
					cw=rm,cb=0;
				}
				else cw+=vf.ss;
			}
			else cw+=vf.ss;			
		}
	}
	return ans;
}
int main(void){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int t; cin>>t;
	while(t--){
		ll b=0,w=0;
		int n; cin>>n;
		v.clear();
		for(int i=0;i<n;i++){
			ll x; char c; cin>>x>>c;
			v.pb({c,x});
			if(c=='B') b+=x;
			else w+=x;
		}
		if(b==0 || w==0){
			if(b==0) cout<<w<<'\n';
			else cout<<b<<'\n';
			continue;
		}
		ll g=gcd(b,w);
		cout<<brick(b/g,w/g)<<'\n';
	}
	return 0;
}