R623(Div.2) B. Homecoming

 

코포할때 풀어서 맞은줄알았는데 56번 테케에서 틀렸다~~!

long long 썼어야하는데 안써서 틀렸다~~!

 

문제를 푸는 방법은 그냥 앞에서부터 쭉 봤다

같은 문자열 더미는 하나라고 생각하면 된다

 

1~n까지 가는데 드는 총 비용을 먼저 구하자

이 부분에서 long long 나올 수 있다..!

 

그리고 앞에서부터 보면서 한 더미씩 안갔을 때 총합이 p보다 작은지 확인하자!

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
int main(){
    int t; scanf(" %d",&t);
    while(t--){
        ll a,b,p; scanf(" %lld %lld %lld",&a,&b,&p);
        string s; 
        cin>>s;
        int answer=s.size();
        if(p<a && p<b){
            printf("%d\n",(int)s.size()); continue;
        }
        ll aSum=0,bSum=0;
        int sz = s.size();
        vector<pair<char,int>> vt;
        for(int i=0;i<sz-1;i++){
            if(s[i]=='A'){
                int j=i;
                while(j<sz-1&&s[j]=='A')j++;
                aSum+=(ll)a;
                vt.push_back({'A',i});
                i=j-1;
            }
            else{
                int j=i;
                while(j<sz-1&&s[j]=='B')j++;
                bSum+=(ll)b;
                vt.push_back({'B',i});
                i=j-1;
            }
        }
        if(aSum+bSum<=p) {
            puts("1"); continue;
        }
        ll sum =aSum+bSum;
        for(int i=0;i<(int)vt.size();i++){
            ll cost = (vt[i].first=='A') ? a:b;
            sum-=cost;
            if(sum<=p){
                int next = i+1;
                if(next<(int)vt.size()){
                    answer = vt[next].second+1;
                    break;
                }
                else{
                    answer =(int)s.size(); break;
                }
            }
        }
        printf("%d\n",answer);
    }
}

 

 

이분탐색으로도 풀 수 있다!

위치를 mid값으로 주고 찾아보자!!

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int t,n;
int a,b,p;
string s;
bool solve(ll mid){
    ll sum=0;
    for(int i=mid;i<n-1; ){
        sum+=(s[i]=='A') ? (ll)a:(ll)b;
        int j=i;
        while(j<n-1 && s[i]==s[j])j++;
        i=j;
    }
    return(sum<=p);
}
int main(){
    //freopen("input.txt","r",stdin);
    scanf(" %d",&t);
    while(t--){
        scanf(" %d %d %d",&a,&b,&p);
        cin>>s; 
        n =s.size();
        int ans=1e9;
        int l=0,r=n-1;
        while(l<=r) {
            int mid = (l+r)/2;
            if(solve(mid)){
                ans = min(ans,mid);
                r = mid-1;
            }
            else l=mid+1;
        }
        printf("%d\n",ans+1);
    }
}