[C++][BOJ 17615] 볼 모으기

[문제]

17615번: 볼 모으기 (acmicpc.net)

17615번: 볼 모으기

---

[문제 풀이]

간단한 그리디 문제이다.

공을 우측으로 모두 밀어넣을때 파란색(B)의 갯수를 센다면 R이 나온 이후에 B가 총 몇개가 있는지를 세면 된다.

반대로 빨간색(R)의 경우는 B가 나온 이후에 R이 몇개가 있는지를 세면 된다.

 

나는 해당 코드를 count_R라는 변수를 만든 뒤 B가 나오면 count_R를 1로 두고 B를 세는 변수에 계속해서 count_B를 더하게 만들었다.

만약에 R가 나오기 전에 B가 나온다면 count_R의 초깃값인 0을 더해서 아무런 상관이 없게 만들었다.

 

*주의사항 : 우측 뿐만 아니라 좌측도 계산을 해줘야 한다. 나는 처음에 우측만을 계산해 줘서 15점이 나왔었다.

---

[코드]

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int solve(string str){
    int answer = 0;
    int max_B = 0;
    int count_R = 0;
    int max_R = 0 ;
    int count_B = 0;

    for(int i = str.size() - 1;i >= 0;i--){
        if(str[i] == 'B'){
            count_B = 1;
            max_B += count_R;
        }
        else if(str[i] == 'R'){
            count_R = 1;
            max_R += count_B;
        }
    }
    answer = min(max_B, max_R);
    max_B = 0;
    max_R = 0;
    count_B = 0;
    count_R = 0;

    for(int i = 0;i < str.size();i++){
        if(str[i] == 'B'){
            count_B = 1;
            max_B += count_R;
        }
        else if(str[i] == 'R'){
            count_R = 1;
            max_R += count_B;
        }
    }
    answer = min(answer,max_B);
    answer = min(answer,max_R);
    return answer;
}


int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    cout<<solve(s)<<endl;

    return 0;
}

처음에 15점이 뜨길래 풀이가 아니라 string 한계가 1000이하인가? 하고 착각을 했다...