각 종류의 개수가 서로 다르면 전달할 수 없다. 개수가 같다면 항상 가능하다. 다음에 전달할 종류를 라 하자. 각 스택이 단색이고, 두 스택이 모두 비어 있지 않다면 그 종류가 서로 다르다는 불변식을 유지한다.
두 번째 스택의 종류가 이면 2, 첫 번째 스택의 종류가 이면 12를 실행한다. 두 경우 모두 불변식이 유지된다. 어느 스택에도 가 없으면 아직 읽지 않은 입력에서 가 반드시 존재한다. 입력을 차례로 읽으며 를 만나면 012로 즉시 전달한다.
그전에 만나는 다른 종류 는 버퍼에 넣는다. 두 번째 스택이 를 담고 있으면 01을 실행한다. 그렇지 않고 첫 번째 스택이 비었거나 종류가 이면 0을 실행한다. 나머지 경우에는 두 번째 스택이 반드시 비어 있으므로 01로 넣는다. 실제로 두 스택이 모두 차 있고 와 종류가 모두 다르다면, 세 종류뿐이므로 한 스택은 를 담아야 하여 앞의 가정과 모순이다. 두 번째 스택의 같은 종류를 먼저 확인해야 같은 종류를 두 스택으로 나누지 않는다.
각 빼빼로는 입력에서 첫 번째 스택, 두 번째 스택, 출력으로 한 번씩만 이동하므로 명령은 정확히 개이고 시간·공간은 이다. 첫 서브태스크는 가능한 상태를 메모하며 세 명령을 완전탐색한다. 상태 수는 이하이고 문자열 처리까지 시간 상한으로 에서 충분하다. 두 번째 서브태스크에서는 첫 번째 스택만 버퍼로 사용하고 원하는 종류를 만날 때까지 입력을 넣는 풀이가 가능하다. 종류가 두 개뿐이면 전달 직후 남은 첫 번째 스택은 항상 단색이다.
Solution written by GPT6.1
