boj 10453 : String Transformation (문자열 변환)

boj 10453 : String Transformation (문자열 변환)

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

A,B는 모두 좋은문자열이다.

그러므로 A 에서 B로 바꾸는 과정은 모두 좋은문자열이다. 왜그럴까?

A가 좋은 문자열이면 임의의 위치 i를 잡는다면 i전까진 b보다 a가 많고, i부터 끝까진 a보다 b가 많기 때문.

따라서 A,B모두 좋은 문자열이라면 A에서 B로 최소이동으로 바꾸는 경로 또한 모두 좋은문자열이다.(정확한 증명은 안되었다..ㅜㅜ 직관적으로....)

그렇다면 이제, A를 B로 옮기기 위한 최소 이동횟수를 구해보자.

예제의 aabbabab -> aaaabbbb 를 생각해보자.

편의를 위해 b를 공백으로 생각하고, a만을 움직인다 생각해도 문제는 변함이 없다.

그렇다면 문제는

aa__a_a_ -> aaaa____

위와같이 단순화된다.

a는 각각 1,2,5,7의 위치에 있고 이를 각각 1,2,3,4의 위치로 옮겨주기만 하면 된다.

-1을 답으로 내는 경우는 없으므로 위의 이동횟수만을 고려해주면된다.