2131번 - 로봇 명령 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 118 | 15 | 12 | 30.000% |
문제
한 회사에서 지뢰 탐사용 로봇을 출시하였다. 이 회사의 로봇 제품은 명령에 따라 움직이거나, 혹은 돌거나, 혹은 지뢰를 찾아보게 된다. 이러한 명령은 총 네 가지 종류로 정리되어 있는데, 각각은 다음과 같다.
- Forward : 로봇이 한 칸 앞으로 이동한다.
- Turn Left : 로봇이 왼쪽으로 90도만큼 회전한다.
- Turn Right : 로봇이 오른쪽으로 90도만큼 회전한다.
- Scan : 로봇의 한 칸 앞에서 지뢰를 찾아본다.
회전은 90도 단위로 하게 되는데, 이는 로봇의 성능의 한계 때문에 지형을 격자 형태로 인식하여 처리하기 때문이다. 또한, 회전을 항상 90도 단위로 해야 하기 때문에 뒤로 돌기 위해서는 두 번의 회전 명령을 내려야 한다.
지뢰 탐사에 로봇을 사용하는 아이디어가 획기적이었기 때문에, 여러 국가의 국방부에서 이 로봇에 대한 관심을 보이게 되었다. 하지만 중국에서 이 로봇과 똑같은 제품을 더 싼 가격에 내놓게 되었고, 이에 대응하기 위해 회사에서는 새로운 로봇 개발에 박차를 가하였다. 새로운 로봇은 다음의 두 종류의 명령에 따라 움직이게 된다.
(1) Move [방향] [N] : 로봇이 [방향] 쪽으로 [N]칸 이동한다. [방향]은 Forward, Back, Left, Right 중의 하나이며 N은 양의 정수이다. 만약 [방향]이 Forward가 아니라면, 그 쪽으로 먼저 회전을 한 뒤에 움직이게 된다(움직인 뒤에는 회전한 방향을 유지한다). (2) Scan [방향] : 로봇이 [방향] 쪽의 한 칸 앞에서 지뢰를 찾아본다. [방향]은 Forward, Back, Left, Right 중의 하나이다. 만약 [방향]이 Forward가 아니라면, 그 쪽으로 먼저 회전을 한 뒤에 지뢰를 찾아보게 된다(지뢰를 찾아본 뒤에는 회전한 방향을 유지한다).
회사 측에서는 명령의 종류를 줄여서 더욱 효율적으로 지뢰 탐사를 수행할 수 있다는 사실을 홍보하려 한다. 이를 위해서 구형 로봇을 동작시키기 위해 필요한 명령 회수와, 똑같은 작업을 수행하기 위한 신형 로봇의 명령 회수를 비교해 보려 한다.
구형 로봇에서 수행한 명령들이 주어졌을 때, 이와 같은 동작을 하도록 하기 위해 신형 로봇에 입력해야 하는 최소 개수의 명령을 찾아내는 프로그램을 작성하시오. 구형 로봇과 신형 로봇은 같은 위치에서, 같은 방향을 향해 있는 상태에서 동작을 시작하며, 지뢰들을 같은 순서대로, 같은 위치를 찾아보아야 한다. 중간에 지나는 위치는 다르더라도 Scan을 수행하는 위치만 일치하면 되는 것으로 한다. 또, 만약 같은 위치에 대해서 여러 번 Scan을 수행하는 입력이 주어진다면, 출력 역시 같은 위치에 대해서 여러 번 Scan을 수행해야 한다. 로봇 자체는 지뢰에 대한 방어 장치가 있기 때문에, Scan을 수행해야 하는 위치를 지나 갈 수도 있다.
입력
첫째 줄에 구형 로봇에서 수행한 명령의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각각의 명령이 위에 있는 형식대로, 한 줄에 하나씩 주어진다.
출력
첫째 줄에 신형 로봇에서 필요한 최소 개수의 명령을 출력한다.
예제 입력 1
8 Forward Forward Turn Left Forward Scan Turn Right Scan Forward
예제 출력 1
4
출처
ICPC > Regionals > Asia East Continent > China > Hangzhou > Hangzhou Regional Contest 2005 I번
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호