문자열에서 a의 개수를 ac 라고 할때, 시작점을 문자열의 맨처음부터 맨 끝까지 이동하면서, 길이가 ac인 문자열을 안에 b가 몇개있는지 검사한다.
이때 검사한 b의 개수 중 최소가 필요한 최소의 교환횟수
쉽게 말해서, 길이가 ac인 문자열 안에 b를 최소로 포함한 문자열을 a로 채우는 문제로 치환한 것이다.
코드
#include <iostream>using namespace std;string str;int ans = 2000000000;int min(int a,int b) { return a < b ? a : b;}void solve(int s, int length) { int bc = 0; for (int i = s; i < s + length; i++) { if (str[i % str.size()] == 'b') bc++; } ans = min(ans, bc);}int main() { cin >> str; int ac = 0; for (int i = 0; i < str.size(); i++) { if (str[i] == 'a') ac++; } for (int i = 0; i < str.size(); i ++) { solve(i, ac); } cout << ans;}