https://www.acmicpc.net/problem/5002
시간 제한 | 메모리 제한 | sovled.ac 티어 |
1초 | 128MB | 실버 1 |
문제
정인이는 강남의 유명한 클럽 Top Root의 도어맨이다. 클럽의 사장은 정인이에게 클럽이 꽉찼을 때, 클럽에 있는 남자와 여자의 수는 거의 비슷해야 한다고 말해주었다.
사람들은 클럽이 문을 열기 전 부터 줄을 서 있는다. 클럽이 문을 열면, 한 명씩 직접 정인이가 입장시켜 준다. 정인이는 그들이 줄을 순서를 바탕으로 입장시켜 준다. 이때, 항상 첫 번째에 있는 사람을 입장시켜야 하는 것은 아니다. 정인이는 재량을 발휘하여 두 번째로 줄 서있는 사람을 첫 번째 사람보다 먼저 입장을 시켜줄 수 있다. 물론 이런 상황이 자주 발생하면 앞 사람이 매우 짜증이 날 것이고, 정인이에게 시비를 걸 수도 있다. 하지만, 정인이는 모든 싸움을 이길 수 있는 사람이기 때문에 이런 걱정은 하지 않아도 된다.
안타깝게도, 정인이는 이렇게 싸움은 잘하지만, 숫자 계산은 잘 하지 못한다. 정인이는 항상 클럽에 들어가있는 남자와 여자의 차이를 머리속에 계산하고 있어야 한다. 이 차이가 정인이가 기억할 수 있는 값보다 크게 된다면 남은 사람들은 클럽에 입장을 할 수 없게 된다.
줄을 서 있는 순서와 정인이가 기억할 수 있는 차이의 최댓값이 주어졌을 때, 클럽에 있는 사람의 수의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정인이가 기억할 수 있는 가장 큰 차이 X<100이 주어진다. 둘째 줄에는 줄을 서 있는 순서가 주어진다. W는 여성, M은 남성을 나타내며, 길이는 최대 100이다. 가장 왼쪽에 있는 글자가 줄의 가장 앞에 서 있는 사람의 성별이다.
출력
클럽에 있는 사람 수의 최댓값을 출력한다.
남성, 여성의 숫자를 각각 세고, 차이를 측정한 후에, 이를 최대 차이랑 비교하면서 들여보낸다. 이때 최대 차이를 넘어서는 경우, 뒷사람이랑 바꿔본다.
#include <bits/stdc++.h>
using namespace std;
int main () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int m = 0; // 남성
int w = 0; // 여성
int temp_diff = 0; // 현재 차이
int diff; // 최대 차이
string line;
cin >> diff >> line;
for(int i = 0; i < line.length(); i++) {
if(line[i] == 'M') m++;
else w++;
temp_diff = abs(m - w);
if(temp_diff > diff) {
// 맨 마지막 사람인 경우 뒷사람이 없으니 그냥 들여보내지 않는다.
if(i == line.length() - 1) {
if(line[i] == 'M') m--;
else w--;
break;
}
else { // 맨 마지막 사람이 아닌 경우
// 뒷사람이랑 성별이 같다면 바꿀이유가 없기 때문에 들여보내지 않는다.
if(line[i] == line[i + 1]) {
if(line[i] == 'M') m--;
else w--;
break;
}
else { // 성별이 다르면 바꿔서 들여보낸다.
if(line[i] == 'M') m--;
else w--;
swap(line[i], line[i + 1]);
i--;
}
}
}
}
cout << m + w;
}
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 5597번 C++ 풀이 (0) | 2022.02.06 |
---|---|
백준 1456번 C++ 풀이 (0) | 2022.02.06 |
백준 11047번 C++ 풀이 (0) | 2022.02.02 |
백준 5397번 C++ 풀이 (0) | 2022.02.02 |
백준 18917번 C++ 풀이 (0) | 2022.01.27 |