오래된 화성 탐사선 한 대가 임무를 거의 마치고, 화성 표면을 도는 마지막 탐사 명령을 기다리고 있다. 탐사 팀은 경로를 이미 정했고, 마지막 명령을 탐사선에 전송하는 일을 당신에게 맡겼다. 경로는 북, 남, 동, 서 네 방향의 이동을 차례로 나열한 것이고, 각 이동은 N, S, E, W 문자 하나로 전송한다.
문제는 전력이다. 신호를 받을 때마다 탐사선의 전력이 줄어드는데, 남은 양이 이미 위험할 만큼 적다. 다행히 제작진은 경로에 반복이 많을 때를 대비해 매크로 하나를 정의하는 기능을 넣어 두었다. 매크로는 쓰지 않아도 된다.
매크로를 쓰는 메시지는 문자열 두 개로 이루어진다. 첫 번째 문자열은 N, S, E, W, M으로 이루어지며 이동과 매크로 호출(M)을 나열한다. 두 번째 문자열은 N, S, E, W로 이루어지며 M이 펼쳐질 내용을 정한다. 예를 들어
WNMWMME
EEN
는 다음 경로를 나타낸다.
WNEENWEENEENE
매크로를 쓴 쪽은 문자 10개만 보내면 되지만, 원래 경로를 그대로 보내려면 13개가 필요하다.
전송 비용은 보낸 문자의 총 개수, 즉 두 문자열의 길이를 더한 값이다. 매크로를 쓰지 않으면 경로를 그대로 한 번만 보내므로 비용은 경로의 길이와 같다. 경로가 주어질 때 전송에 필요한 최소 문자 개수를 구하라.
cho.sh