[백준 12904번 / C++] A와 B

그리디 문제이다. 

 

#접근 방법

 

처음에 문제를 읽어봤을 때 이걸 어떻게 해야하지..? 생각이 들수도 있다.

 

나도 그랬다. 

 

문자열 S에 언제 A를 추가해야할지, 또는 언제 B를 추가하고 뒤집어야하는지.. 

 

한 3분정도 생각하다가 답이 안나와서 만들어야 할 문자열에서 A와 B를 빼면 되지 않을까? 라는 생각이 들었다.

 

한번쯤은 직관적으로 문제에 접근해도 좋지만 만약 안풀린다면 추가하는 것이 아니라 반대로 생각해서 빼보는 방식도 고려해봐야할 것이다. 

 

즉, 문자열 S1에서 만들어야 할 문자열이 S2 라면, 

 

S2에서 A를 빼주고, 또는 B를 빼주고 문자열을 뒤집는다. 

 

언제동안? S1과 S2의 길이가 같을때까지!

 

문자열의 길이가 같아졌을 때 같은 문자열이 맞는지 비교해서 출력하면 끝이다. 

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std; 

int main() {
	string s1, s2; 
	cin >> s1 >> s2; 
	int idx = s2.size() - 1; 
	while (s1.size() < s2.size()) {

		if (s2[idx] == 'A')s2.pop_back(); 
		else {
			s2.pop_back(); 
			reverse(s2.begin(), s2.end()); 
		}
		idx--; 

	}
	if (s1 == s2)cout << 1;
	else cout << 0;  
}

 

12904번: A와 B