[백준, C++] 17615 - 볼 모으기

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

17615번: 볼 모으기

 

문제 분석

더욱 최적의 해가 있겠지만, 일단은 무식한 완전 탐색으로 풀었다.

 

빨간/파란 공을 왼/오른쪽에 모을 수 있다. 이 때, 공을 이동할 횟수는 이렇다.

 

만일 빨간 공을 왼쪽으로 모은다면, 공을 이동하는 횟수는 가장 왼쪽에 모여있는 빨간 공을 모두 제거한 후 남은 빨간 공의 개수 이다.

 

왜냐, 이미 왼쪽에 모여있는 빨간 공은 굳이 건드릴 필요가 없기 때문이다. 그리고 남은 빨간 공은, 가운데에 파란 공 사이에 둘러싸인 빨간 공 중 가장 왼쪽에 있는 것부터 차례로 왼쪽으로 모아버리면 되기 때문이다.

 

이렇게 푼 이유는 사실 시간 초과가 안 날 것이라는 확신이 있기 때문이었다. 시도해 볼 케이스는 빨/파 그리고 왼/오 이기 때문에 총 4개이고, 각 케이스에서는 끽해야 50만 번의 연산을 할 것이기 때문에 200만 번의 연산을 해도 1초 안에 끝나니 문제가 없을 거란 생각이었다.

 

코드

#include <iostream>
#include <cstring>

using namespace std;

int n;
string input;
int result = 500001;

void calculateMovedCount(bool toLeft, bool isRed) {
    if (toLeft) {
        // 공을 왼쪽으로 옮기는 경우
        if (isRed) {
            // 빨간 공을 옮기는 경우
            string str = input;
            if (str[0] == 'R') {
                int pos = 0;
                for (int i = 1; i < str.length(); i++) {
                    if (str[i] == 'R') {
                        pos = i;
                    } else {
                        break;
                    }
                }
                str.erase(0, pos + 1);
            }

            int count = 0;
            for (int i = 0; i < str.length(); i++) {
                if (str[i] == 'R') {
                    count++;
                }
            }

            result = min(result, count);
        } else {
            // 파란 공을 옮기는 경우
            string str = input;
            if (str[0] == 'B') {
                int pos = 0;
                for (int i = 1; i < str.length(); i++) {
                    if (str[i] == 'B') {
                        pos = i;
                    } else {
                        break;
                    }
                }
                str.erase(0, pos + 1);
            }

            int count = 0;
            for (int i = 0; i < str.length(); i++) {
                if (str[i] == 'B') {
                    count++;
                }
            }

            result = min(result, count);
        }
    } else {
        // 공을 오른쪽으로 옮기는 경우
        if (isRed) {
            // 빨간 공을 옮기는 경우
            string str = input;
            if (str[str.length() - 1] == 'R') {
                int pos = str.length() - 1;
                for (int i = str.length() - 2; i >= 0; i--) {
                    if (str[i] == 'R') {
                        pos = i;
                    } else {
                        break;
                    }
                }
                str.erase(pos, str.length());
            }

            int count = 0;
            for (int i = 0; i < str.length(); i++) {
                if (str[i] == 'R') {
                    count++;
                }
            }

            result = min(result, count);
        } else {
            // 파란 공을 옮기는 경우
            string str = input;
            if (str[str.length() - 1] == 'B') {
                int pos = str.length() - 1;
                for (int i = str.length() - 2; i >= 0; i--) {
                    if (str[i] == 'B') {
                        pos = i;
                    } else {
                        break;
                    }
                }
                str.erase(pos, str.length());
            }

            int count = 0;
            for (int i = 0; i < str.length(); i++) {
                if (str[i] == 'B') {
                    count++;
                }
            }

            result = min(result, count);
        }
    }
}

void getInput() {
    cin >> n;
    cin >> input;
}

void solve() {
    calculateMovedCount(true, true);
    calculateMovedCount(true, false);
    calculateMovedCount(false, true);
    calculateMovedCount(false, false);
}

void printResult() {
    cout << result << "\n";
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    getInput();
    solve();
    printResult();

    return 0;
}

 

코드 설명

정말 4가지 경우를 다 따져봤다.

 

1. 빨간 공을 왼쪽에 모으는 경우

2. 파란 공을 왼쪽에 모으는 경우

3. 빨간 공을 오른쪽에 모으는 경우

4. 파란 공을 오른쪽에 모으는 경우

 

그리고 4가지 경우에서 가장 작은 결과를 뽑아내 출력하도록 했다.

 

추가

코드가 너무 마음에 안 들어서 고쳤다.

#include <iostream>
#include <cstring>

using namespace std;

int n;
string input;
int result = 500001;

void getInput() {
    cin >> n;
    cin >> input;
}

void solve() {
    // 1. 색상 별 공의 개수 확인
    int redCount = 0;
    int blueCount = 0;
    for (char c : input) {
        if (c == 'R') {
            redCount++;
        } else if (c == 'B') {
            blueCount++;
        }
    }

    // 2. 왼쪽으로 공을 모으는 경우
    char leftColor = input[0];
    int count = 0;
    for (int i = 0; i < input.length(); i++) {
        if (input[i] == leftColor) {
            count++;
        } else {
            break;
        }
    }

    if (leftColor == 'R') {
        result = min(result, min(blueCount, redCount - count));
    } else if (leftColor == 'B') {
        result = min(result, min(redCount, blueCount - count));
    }

    // 3. 오른쪽으로 공을 모으는 경우
    char rightColor = input[input.length() - 1];
    count = 0;
    for (int i = input.length() - 1; i >= 0; i--) {
        if (input[i] == rightColor) {
            count++;
        } else {
            break;
        }
    }

    if (rightColor == 'R') {
        result = min(result, min(blueCount, redCount - count));
    } else if (rightColor == 'B') {
        result = min(result, min(redCount, blueCount - count));
    }
}

void printResult() {
    cout << result << "\n";
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    getInput();
    solve();
    printResult();

    return 0;
}

사실 같은 기능을 하는 코드인데, 처음 작성한 코드는 너무 가독성 면에서도 별로고, 불필요하게 메모리를 너무 쓰는 것 같아 수정했다.