https://www.acmicpc.net/problem/25057
25057번: Evolution of Weasels
A wild basilisk just appeared at your doorstep. You are not entirely sure what a basilisk is and you wonder whether it evolved from your favorite animal, the weasel. How can you find out whether basilisks evolved from weasels? Certainly, a good first step
www.acmicpc.net
문제 요약
문자열에 AA, BB, CC, ABAB, BCBC를 추가하거나 삭제하여 변형할 수 있다. 두 문자열이 주어졌을 때, 잘 변형하여 같게 만들 수 있는가?
풀이
작은 길이의 문자열에 대해 써보다보면, 아래끼리는 같은 종류의 문자열임을 알 수 있다. 즉, 변형하여 같게 만들 수 있다.
- AB, BA
- BC, CB
위 관찰을 이용하여, B는 항상 한 곳으로 몰아줄 수 있다.
AC, CA는 아쉽지만, 변형하여 같게 만들 수 없다.
AA, BB, CC를 삭제할 수 있으므로, 각 위치에서의 연속된 A, B, C 개수 기우성만 유지하여 만든 문자열을 비교하여 답을 구할 수 있다.
느낀 점
관찰이 꽤나 어렵다.
'PS' 카테고리의 다른 글
| [BOJ] 24532번 : 트리와 XOR 쿼리 (2) | 2024.01.25 |
|---|---|
| [AtCoder] E - Digit Sum Divisible (5) | 2024.01.15 |
| 스택인가? (0) | 2023.07.21 |
| PS 근황과 계획 (4) | 2023.05.14 |
| "map병장 메모리제한에 패배" (2) | 2023.05.05 |