https://www.acmicpc.net/problem/17615
빨간색 볼과 파란색 볼이 <그림 1>에서 보인 것처럼 일직선상에 섞여 놓여 있을 때, 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다. 볼을 옮기는 규칙은 다음과 같다.
예를 들어, 처음에 볼이 <그림 1>에서 보인 것처럼 있을 때, 빨간 볼을 <그림 2>에서 보인 것처럼 옮긴 후, <그림 3>에서 보인 것처럼 옮긴다면 두 번 만에 같은 색끼리 모을 수 있다.
반면에 파란색 볼을 선택하여 에서 보인 것처럼 옮기면(화살표에 있는 수는 옮기는 순서를 나타낸다) 네 번을 옮겨야 같은 색의 볼끼리 모을 수 있다.
일직선상에 놓여 있는 볼에 관한 정보가 주어질 때, 규칙에 따라 볼을 이동하여 같은 색끼리 모으되 최소 이동횟수를 찾는 프로그램을 작성하시오.
첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주어질 수도 있으며, 이 경우 답은 0이 된다.
최소 이동횟수를 출력한다.
번호 | 배점 | 제한 |
---|---|---|
1 | 15 | N ≤ 10 |
2 | 22 | N ≤ 1,000 |
3 | 14 | N ≤ 500,000, 처음 상태에서 모든 파란 공은 연속해서 존재한다. |
4 | 49 | 원래의 제약조건 이외에 아무 제약조건이 없다. |
9
RBBBRBRRR
2
8
BBRBBBBR
1
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
string data;
cin >> data;
int answer = 987654321;
int seq = 0;
int count = 0;
for(int i = 0; i < data.length(); i++){
if(data[i] == 'R') seq = 1;
if(seq == 1 && data[i] == 'B') count++;
}
answer = min(answer, count);
seq = 0;
count = 0;
for(int i = 0; i < data.length(); i++){
if(data[i] == 'B') seq = 1;
if(seq == 1 && data[i] == 'R') count++;
}
answer = min(answer, count);
seq = 0;
count = 0;
for(int i = data.length() - 1; i >= 0; i--){
if(data[i] == 'R') seq = 1;
if(seq == 1 && data[i] == 'B') count++;
}
answer = min(answer, count);
seq = 0;
count = 0;
for(int i = data.length() - 1; i >= 0; i--){
if(data[i] == 'B') seq = 1;
if(seq == 1 && data[i] == 'R') count++;
}
answer = min(answer, count);
cout << answer << '\n';
}
전형적인 빡구현 + 그리디 문제라고 생각한다. 경우는 총 네가지다.
1. 빨간색을 오른쪽으로
2. 빨간색을 왼쪽으로
3. 파란색을 오른쪽으로
4. 파란색을 왼쪽으로
각 경우에 따라 결론을 내서 최솟값을 도출하면 되는데 상당히 노가다성이 심한 문제다.