맨해튼 택배 로봇

시간 제한1초메모리 제한1024 MB

요약

N, E, S, W 방향으로 이동한 기록이 주어질 때, 창고로 돌아가는 최소 걸음 수를 구합니다.

문제

맨해튼 한 지역에서 택배 로봇이 운영된다. 이 로봇은 크기가 꽤 크고, 한 번에 여러 개의 택배를 서로 다른 목적지로 배달할 수 있다. 모든 택배를 배달한 뒤에는 로봇이 창고로 돌아가 새 택배를 받아야 한다.

맨해튼의 도로는 격자 모양이다. 모든 도로는 정확히 남북 방향이거나 동서 방향이다. 또한 나란히 있는 평행한 도로 사이의 간격은 모두 같다.

로봇의 한 걸음은 교차로 하나에서 도로를 따라 다음 교차로까지 이동하는 것을 뜻한다.

로봇이 창고로 돌아갈 수 있는 최소 걸음 수를 구하라.

첫 줄에 로봇이 지금까지 한 걸음의 수 $N$ 이 주어진다 ( $1 \le N \le 1\,000$ ). 둘째 줄에는 각 걸음의 방향을 나타내는 $N$ 개의 문자가 주어진다. N은 북쪽, E는 동쪽, S는 남쪽, W는 서쪽 방향이다.

한 줄에 로봇이 창고로 돌아갈 수 있는 최소 걸음 수를 출력한다.