Bob은 절대 이길 수 없으니까 Draw 만들 수 있는지만 생각하면 되고, Alice가 뭘 고르던 똑같은 문자열을 가져가는 걸 목표로 게임을 해야 함. 그러려면 크게 두 가지가 가능한데,
1. 팰린드롬이라 앞 뒤로 같은 거 가져가기가 가능함 ex) abccba
2. 똑같은게 두개씩 뭉쳐있어서 같은거 무조건 가져가기가 가능함 ex) aabbcc
겉부분만 팰린드롬이고 안쪽은 두개씩 뭉쳐있어도 가능 ex)caabbc
이렇게만 Draw하고 나머지는 Alice 승리!
나도 이렇게함
첨에 이렇게 생각했었는데 모든 경우를 커버할 수 있을까 확신이 안 생겨서 다르게 풂
무지성 2차원 dp보다 멋있네 이거 hard로 내도 됬겠는데? - dc App
저렇게 짰다고 생각했는데 잘못 짰나보네