17615번 볼 모으기

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

처음 생각은 dfs를 떠올렸으나, 바로 dfs를 할 필요가 없음을 알았다.

그리고 정렬도 생각했으나, 이 때에는 R, B 모두 움직이므로 불가능했다.

그래서 다시 생각을 해봤을 때

R만 움직여서 R들을 맨 왼쪽으로 옮길 것인지, 맨 오른쪽으로 옮길 것인지

B만 움직여서 B들을 맨 왼쪽으로 옮길 것인지, 맨 오른쪽으로 옮길 것인지

위의 4가지 경우의 수가 있었다.

각 경우를 잘 구현하면 된다.

물론,  vc의 첫 원소와 맨 마지막 원소에 따라서 잘 대처(?)해주면 된다.

코드가 길어 보이는 것은 착각일 수도 있다.

#include <bits/stdc++.h>
 
using namespace std;
 
int n, cnt, ans = 2e9;
vector<char> vc;
vector<int> rc, bc;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
    scanf("%d", &n);
    getchar();
 
    char c;
    int redc = 0, bluec = 0;
 
    for (int i = 0; i < n; i++) {
        scanf("%c", &c);
        vc.push_back(c);
 
        if (c == 'R') {
            if(bluec) bc.push_back(bluec);
            bluec = 0;
            ++redc;
        }
        else if (c == 'B') {
            if(redc) rc.push_back(redc);
            redc = 0;
            ++bluec;
        }
    }
 
    if (bluec) bc.push_back(bluec);
    if (redc) rc.push_back(redc);
 
    if (rc.empty() || bc.empty()) {
        printf("0\n");
        return 0;
    }
 
    int Left = 2e9, Right = 2e9;
 
    // R만 움직임
    int total_red = accumulate(rc.begin(), rc.end(), 0);
    
    // R을 맨 왼쪽으로만 옮겼을 때
    if (vc[0] == 'R') {
        Left = total_red - rc[0];
    }
    else {
        Left = total_red;
    }
 
    // R을 맨 오른쪽으로만 옮겼을 때
    if (vc[vc.size() - 1] == 'R') {
        Right = total_red - rc[rc.size() - 1];
    }
    else {
        Right = total_red;
    }
 
    ans = min(Left, Right);
 
    Left = Right = 2e9; // 최솟값을 구하기 위함
 
    // B만 움직임
    int total_blue = accumulate(bc.begin(), bc.end(), 0);
 
    // B를 맨 왼쪽으로
    if (vc[0] == 'B') {
        Left = total_blue - bc[0];
    }
    else {
        Left = total_blue;
    }
 
    // B를 맨 오른쪽으로
    if (vc[vc.size() - 1] == 'B') {
        Right = total_blue - bc[bc.size() - 1];
    }
    else {
        Right = total_blue;
    }
 
    printf("%d\n", min(ans, min(Left, Right)));
 
    return 0;
}