Codeforces Round #744 (Div. 3)-A. Casimir's String Solitaire
falconlee236
·2021. 11. 27. 09:46
문제 설명
시저는 대문자 'A', 'B', 'C'로만 이루어진 문자열 $s$를 생각하고 있다. 각 차례마다 다음 두 행동을 하나 선택해서 할 수 있다.
- 임의의 위치에 있는 문자 'A'와 문자 'B'를 동시에 제거한다.(이 문자는 인접할 필요가 없다.)
- 임의의 위치에 있는 문자 'B'와 문자 'C'를 동시에 제거한다.(이 문자는 인접할 필요가 없다.)
따라서 문자열의 길이는 차례가 한번 지날때 마다 2씩 줄어든다.
예를 들어 $s$ = "ABCABC"가 있을 때 시저는 한 차례가 지난후 $s$ = "ACBC"를 얻을 수 있다. (첫번째 등장하는 'B'와 두번째 등장하는 'A'를 제거한다.)
우리가 해야할 일은 문자열 $s$가 주어졌을 때, 위에서 말한 행동을 차례차례 진행해서 빈 문자열을 만들 수 있는지 결정하는 것이다.
Input
첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 1000)$이 주어진다.
각 테스트 케이스에 문자열 $s$가 주어진다. 문자열 $s$는 대문자 'A', 'B', 'C'로 이루어져 있으며 그 길이는 $1$ 부터 $50$ 까지이다.
Output
$t$개 줄을 출력한다. 각 줄은 그와 대응하는 테스트 케이스의 답을 출력해야 한다. 대응하는 문자열이 모두 지워질 수 있으면 "YES"를 출력하고 그렇지 않으면 "NO"를 출력한다.
문자를 출력할때 대문자건 소문자건 상관 없다. (yEs, yes, Yes, YES)모두 가능하다.
Example
input
6
ABACAB
ABBA
AC
ABC
CABCBB
BCBCBCBCBCBCBCBC
output
NO
YES
NO
NO
YES
YES
문제 접근
사용한 알고리즘: 구현
걸린 시간 : 00:04
A번 답게 조금만 생각하면 풀 수 있는 문제이다. 일단 가장 빨리 생각할 수 있는 것은 무조건 2씩 줄어들기 때문에 홀수 길이의 문자열은 절대로 빈 문자열이 될 수 없다는 점이다. 따라서 홀수 문자열인 경우 무조건 "NO"
짝수 문자열인 경우를 생각해보자. 모든 차례에서 무조건 문자 'B'가 사라진다는 점에 주목해보자. 그렇다면 한 차례당 2개씩 문자가 사라지기 때문에 모든 문자를 지우려면 $\frac{n}{2}$ 번의 연산이 필요하다.
여기서 모든 차례에 무조건 문자 'B'가 사라지는데, 모든 문자를 사라지게 하려면 $\frac{n}{2}$ 번의 차례가 필요하다. 그렇다면 문자 'B'가 $\frac{n}{2}$ 개 있다면 이 문자열에 있는 모든 문자를 지울수 있을 것이다.
정답 코드
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
int t; cin >> t;
while(t--){
string str; cin >> str;
if(str.size() % 2 == 1) cout << "NO" <<"\n";
else{
cout << (count(str.begin(), str.end(), 'B') == str.size() / 2 ? "YES" : "NO") << "\n";
}
}
return 0;
}
'알고리즘 > codeforces' 카테고리의 다른 글
Codeforces Round #744 (Div. 3)-C. Ticks (0) | 2021.11.27 |
---|---|
Codeforces Round #744 (Div. 3)-B. Shifting Sort (0) | 2021.11.27 |
Codeforces Round #748 (Div. 3)-E. Gardener and Tree (0) | 2021.11.25 |
Codeforces Round #748 (Div. 3)-D1. All are Same (0) | 2021.11.25 |
Codeforces Round #748 (Div. 3)-C. Save More Mice (0) | 2021.11.24 |