[ boj : 1522] 문자열 교환

www.acmicpc.net/problem/1522

1522번: 문자열 교환

문제 : a와 b만 주어진 문자열이 있고, a를 연다라 놓고 싶을때 최소한으로 교환해야되는 횟수를 구하시오

 

해설 : 이런 문제가 은근히 안보이면 계속 안보입니다. 모든 문제를 접하게 될때 가장 중요한 개념 중 하나는 어떻게 하면 문제를 최대한으로 간소화 시킬 수 있을지 부터 생각해 보는겁니다(djm03178 님의 말씀입니다)

 

그러면 문제를 한번 봅시다.

우린 일단 직관적으로는 누구나 다 알고 있습니다.

"요놈 a랑 요놈 b랑 바꾸고 그다음 요놈이랑........ 그러면 최소로 바꿀 수 있네?" 그런데 문제는 이를 코드로 '논리적'이게 옮기는게 안될 뿐이죠.

 

다시 생각해 보면 직관적으로 접근했던 과정이 에초에 논리적이지 못한 시선으로 바라보았기 때문입니다. 처음으로 돌아가서 직관적으로 생각했던 때를 기억하면 우린 '어떻게 이 문제를 직관적으로 해결했지?'부터 시작해 보는겁니다.

 

a와 b가 무작위로 주어진 문자열을 보고 우린 어떤 a와 어떤 b를 선택해 바꿔줘야 최소의 횟수로 바꿀 수 있을지 알고있는 상태입니다. 그러나,,,,,특정 a와 특정 b를 어떤 조건에 의해 선택을 하고 바꾸어야 되는지 코드로 표현하려고 하면 결코 쉽게 옮길 수가 없다는 걸 알게 되죠. 그럼 이 방법은 과감하게 포기하는 겁니다. 그리고 또 다시 처음으로 돌아갑니다.

 

다시 문제를 읽고 문제속에 담겨져 있는 힌트를 어떻게서든 쥐어짜는 겁니다. 그리고 우린 발견하게 되죠.

"어??문자열의 길이가 1000이 최대네?"

아 그러면 그냥 발생할 수 있는 모든 경우의 수를 다 확인해보는건 어떨까?? 라고 말이죠.

 

근데 여기서 다시 고민에 빠집니다. 흠,,,어떻게 일일이 전부 확인해볼 수 있을까??

a를 연속으로 배치하려면 결국 주어진 문자열에서 a의 개수가 곧 길이가 될 텐데......응? 그러면 시작하는 index부터 a의 문자열 길이만큼 b의 개수를 세면 그게 곧 교환의 횟수가 아닐까???이걸 0번 index 부터 마지막 index까지 반복적으로 수행하면서 최소값을 갱신시켜 주면 되겠네!!!!

 

이렇게 말이죠.

#include<bits/stdc++.h>

using namespace std;

int solve(string& s, int x, int len);

int main()
{
	string s;
	cin >> s;

	int cnt = 0,ans=(int)1e9;
	for (int i = 0; i < s.length(); i++)
		if (s[i] == 'b')cnt++;
	for (int i = 0; i < s.length(); i++)
		ans = min(ans,solve(s, i,cnt));
	cout << ans;
	return 0;
}
int solve(string& s, int x,int len)
{
	int ret = 0;
	for (int i = x; i < x + len; i++)
		if (s[(i+1)%s.length()] == 'a')
			ret++;
	return ret;
}