[BOJ/백준][Silver1] 17615 : 볼 모으기 (C++)

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

17615번: 볼 모으기

 

 

[난이도] Silver1
[유형] Greedy

[풀이]
최종 볼의 상태는 모든 B가 왼쪽, 모든R이 오른쪽인 상태이거나,
R이 왼쪽, 모든 B가 오른쪽인 상태 둘중에 하나입니다.

각 케이스에서 해당 상태를 만드는 경우에는 R을 움직이는 경우, B를 움직이는 경우 두가지가 있습니다.
결국 총 4가지 케이스인데 이것을 각각 해보면 됩니다.

예를 들어 (B~)(R~) 상태를 R을 움직여서 만들려면 이미 오른쪽 끝에 있는 R들을 제외하고 나머지 R들을
1회 움직여서 오른쪽에 붙혀줘야 합니다.
즉 오른쪽 끝에 있는 R을 제외한 모든 R의 개수를 세주면 됩니다.

위 과정을 4가지 케이스에 대해 각각 해줘서 그중 최솟값을 답으로 출력해주면 됩니다.
여러가지 방법이 있겠지만 저는
이미 뭉쳐있는 공들을 pair vector를 이용해 하나의 묶음으로 묶어주었습니다.
예를 들어 RRBRRRBRRRR 이 있을 때,
{ {'R',2} , {'B',1} , {'R',3} , {'B',1} , {'R',4} } 와 같이 vector에 저장하면
모든 R을 오른쪽으로 보낼 때, index의 마지막인 {'R',4}는 무시하고 {'R',2}, {'R',3} 만 오른쪽으로 보내면 되므로
총 5번의 이동이 필요하게 됩니다.

 

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<pair<char,int>> v; 
int N;
string s;
int main(){
    cin >> N >> s;
    for(int i=0;i<s.size();i++){
        int j=i;
        int cnt=0;
        for(;j<s.size();j++){
            if(s[i]==s[j]) cnt++;
            else break;
        }
        v.push_back({s[i],cnt});
        i=j-1;
    }
    int ans,rtmp=0,btmp=0;
    for(int i=1;i<v.size();i++){
        auto [col,cnt] = v[i];
        if(col=='R') rtmp+=cnt;
        else btmp+=cnt;
    }
    ans=min(rtmp,btmp);
    rtmp=0,btmp=0;
    for(int i=v.size()-2;i>=0;i--){
        auto [col,cnt] = v[i];
        if(col=='R') rtmp+=cnt;
        else btmp+=cnt;
    }
    ans=min(ans,btmp);
    ans=min(ans,rtmp);
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/17615.cpp