33975번 - 현대모비스 V2X 자율주행 1

문제

현대모비스는 미래 모빌리티 산업을 선도하는 기업으로 도약하기 위해, 소프트웨어와 하드웨어가 결합된 차별화된 모빌리티 솔루션을 제공하고자 노력하고 있습니다. 이러한 연구개발 및 생산 역량을 바탕으로 스마트 모빌리티, UAM(도심항공모빌리티), 로보틱스 등 다양한 분야로 사업을 확장해 나가고 있습니다.
또한 자율주행 4단계의 핵심 기술인 5G 기반 V2X 통합제어기를 개발하며 기술 선도에 앞장서고 있으며, V2X는 차량 간 또는 차량과 인프라 간의 실시간 통신을 통해 자율주행과 로보택시 등 원격주행 서비스의 안전성과 효율성을 크게 높여줄 핵심 기술로 주목받고 있습니다.

자율주행 기능이 있는 1ドル$번 차량과 2ドル$번 차량이 $(0,0)$에서 $(N,N)$까지 이동하려 한다.

각 차량은 매 초 아래 두 가지 중 한 가지 이동을 선택해 이동할 수 있다.

• R: $x$축 방향으로 1ドル$만큼 이동한다.
• U: $y$축 방향으로 1ドル$만큼 이동한다.

두 차량이 출발점과 도착점을 제외한 점에서 만나면 두 차량이 충돌해 사고가 일어날 수 있으므로 경로를 수정하고자 한다. 다음 연산을 최소로 수행해 출발점과 도착점이 아닌 점에서 두 차량이 만나지 않게 해야 한다.

• $i$ $a$: $i$번 차량의 $a$번째 이동과 $a + 1$번째 이동을 바꾼다. $(1 \le i \le 2;$ 1ドル \le a \lt 2N)$

필요한 연산의 최소 횟수를 구하여라.

입력

첫째 줄에 도착점의 좌표를 나타내는 정수 $N$이 주어진다. $(1 \le N \le 10^5)$

둘째 줄에 1ドル$번 차량의 경로를 나타내는 길이가 2ドルN$인 문자열이 주어진다.

셋째 줄에 2ドル$번 차량의 경로를 나타내는 길이가 2ドルN$인 문자열이 주어진다.

항상 $(N,N)$에 도착할 수 있는 경로만 주어진다.

출력

필요한 연산의 최소 횟수를 출력하라.

제한

힌트