BOJ 24980 - Photoshoot
항상 짝수번째의 prefix만 reverse가 가능하고 $G$를 최대한 짝수에 많이 배정해야 한다.
2개씩 끊어서 GG나 HH는 reverse해도 항상 같이 reverse되고 정답에 영향을 미치지 않기 때문에 모두 삭제한다.
GGGHGHHGHHHGHG -> GHGHHGHGHG
GH를 A라고 HG를 B라고 표기해보자.
GHGHHGHGHG -> AABBB
최대한 HG=B 를 많이 만드는 것이 목적이다.
한 번의 reverse는 새로운 문자열의 prefix를 뒤집은다음 A를 B로, B를 A로 바꾸는 것이다.
우린 최소 횟수를 세므로 동일하게 중복된 것들을 제거한다.
AABBB -> AB
마지막이 B라면 거기 전까지 prefix를 reverse시키면 되므로 제거한다.
AB -> A
이 문자열의 길이가 정답인데, 그 이유는 항상 앞에 세그먼트를 하나 제거하기 위해 최소 하나의 연산이 필요하기 때문이다.
ABAB에서 앞에 두개를 뒤집으면 AB로 동일하기 때문에 의미없고,
첫 번째 A만 B로 변경하면 하나가 준다.
세 번째 A를 골라서 BABB -> BAB 로 해도 결국 BAB -> AAB -> BBB -> B 가 된다.
Comments