[BOJ][백준 12919] A와 B 2 - C++

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

12919번: A와 B 2

백준 사이트의 12919번 문제, A와 B 2 문제다.

본인은 C++로 문제풀이를 진행하였다.

---

0. 문제 읽기

미묘한 N을 가진 문제

• 얼핏 보면 그냥 DFS로 풀면 될 것 같지만 N의 크기가 애매하다.
• DFS로 가게되면 2가지 경우를 최대 50번 수행하므로 2^50번의 시행, 즉 불가능!
• 다른 방법이 필요하다.

---

1. 문제풀이 아이디어

• 문자열 S를 T로 만들지 말고, 반대로 T에서 S를 만들자.
• 재귀적으로 구현한다.
• 다음 재귀문으로 진입하는 조건은 다음과 같다. (공통적으로 아직 정답을 발견하지 않았어야 함)
  1. T의 마지막 문자가 'A'이고, A의 개수가 아직 S의 A개수보다 많으면 A를 제거하고 진입한다.
  2. T의 첫 문자가 'B'이고, B의 개수가 아직 더 줄어야 하면 T를 뒤집은 다음에 B를 제거한다.

---

2. 코드 핵심 부분

1) input 함수,

   이후 재귀함수 실행시에 필요한 변수들을 미리 구해주었다.

// 입력 함수
void input() {
	cin >> S >> T;
	Slen = S.length();
	Tlen = T.length();

	// S와 T에서 A, B의 개수를 구함
	for (int i = 0; i < Slen; i++) {
		if (S[i] == 'A')
			SA++;
		else if (S[i] == 'B')
			SB++;
	}

	for (int i = 0; i < Tlen; i++) {
		if (T[i] == 'A')
			TA++;
		else if (T[i] == 'B')
			TB++;
	}
}

 

2) 재귀적으로 T를 변경하면서 S와 같아지는지 확인하는 함수,

   다음 재귀함수에 진입하는 조건을 3가지 설정하여 최대한 시행을 줄이도록 하였다.

   S의 길이와 T의 길이가 같아짐을 기저조건으로 설정하였다.

// 재귀적으로 T를 변경하면서 S와 같아지는지 확인하는 함수
void solve() {
	// T와 S의 길이가 같을 때
	if (Slen == Tlen) {
		if (S == T) {
			Ans = 1;
		}
		return;
	}

	// T가 S와 같아지지 않았고, T의 마지막 문자가 A이고 A의 개수가 S보다 많을 때
	if (!Ans && T[Tlen - 1] == 'A' && TA > SA) {

		// T의 마지막 문자 A를 제거하고, A의 개수를 1 감소시킴
		T.pop_back();
		Tlen--;
		TA--;

		// 재귀적으로 T를 변경하면서 S와 같아지는지 확인함
		solve();

		// T를 다시 복원함
		T.push_back('A');
		Tlen++;
		TA++;
	}

	// T가 S와 같아지지 않았고, T의 첫 번째 문자가 B이고 B의 개수가 S보다 많을 때
	if (!Ans && T[0] == 'B' && TB > SB) {

		// T를 뒤집은 후, 마지막 문자를 제거하고, B의 개수를 1 감소시킴
		reverse(T.begin(), T.end());
		T.pop_back();
		Tlen--;
		TB--;

		// 재귀적으로 T를 변경하면서 S와 같아지는지 확인함
		solve();

		// T를 다시 복원함
		T.push_back('B');
		Tlen++;
		TB++;
		reverse(T.begin(), T.end());
	}
}

---

3. 전체 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

// 필요한 전역 변수들
string S, T; // 문자열 S, T
int Slen, Tlen; // S, T의 길이
int SA, SB, TA, TB; // S, T에서 A와 B의 개수
int Ans; // 결과값

// 입력 함수
void input() {
	cin >> S >> T;
	Slen = S.length();
	Tlen = T.length();

	// S와 T에서 A, B의 개수를 구함
	for (int i = 0; i < Slen; i++) {
		if (S[i] == 'A')
			SA++;
		else if (S[i] == 'B')
			SB++;
	}

	for (int i = 0; i < Tlen; i++) {
		if (T[i] == 'A')
			TA++;
		else if (T[i] == 'B')
			TB++;
	}
}

// 재귀적으로 T를 변경하면서 S와 같아지는지 확인하는 함수
void solve() {
	// T와 S의 길이가 같을 때
	if (Slen == Tlen) {
		if (S == T) {
			Ans = 1;
		}
		return;
	}

	// T가 S와 같아지지 않았고, T의 마지막 문자가 A이고 A의 개수가 S보다 많을 때
	if (!Ans && T[Tlen - 1] == 'A' && TA > SA) {

		// T의 마지막 문자 A를 제거하고, A의 개수를 1 감소시킴
		T.pop_back();
		Tlen--;
		TA--;

		// 재귀적으로 T를 변경하면서 S와 같아지는지 확인함
		solve();

		// T를 다시 복원함
		T.push_back('A');
		Tlen++;
		TA++;
	}

	// T가 S와 같아지지 않았고, T의 첫 번째 문자가 B이고 B의 개수가 S보다 많을 때
	if (!Ans && T[0] == 'B' && TB > SB) {

		// T를 뒤집은 후, 마지막 문자를 제거하고, B의 개수를 1 감소시킴
		reverse(T.begin(), T.end());
		T.pop_back();
		Tlen--;
		TB--;

		// 재귀적으로 T를 변경하면서 S와 같아지는지 확인함
		solve();

		// T를 다시 복원함
		T.push_back('B');
		Tlen++;
		TB++;
		reverse(T.begin(), T.end());
	}
}

// 결과 출력 함수
void output() {
	cout << Ans;
}

// 메인함수
int main() {

	// 입력 받기
	input();

	// T를 재귀적으로 변경하면서 S와 같아지는지 확인함
	solve();

	// 결과 출력
	output();

	return 0;
}

---

4. 문제 풀이를 마치며..

S를 T로 만드는 건 시간초과, 반대의 경우는 0ms의 실행시간

문제 자체는 직관적이고 간단한 문제다.

그런데도 골드5의 난이도와 30프로의 낮은 정답률인 이유는

그냥 S에서 T로 만드는 것은 불가능하기 때문이다.

 

반대로 T에서 S로 수렴하며 구하는 아이디어가 중요한 문제였다.