2946번 - 알라딘과 램프 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 49 | 10 | 9 | 40.909% |
문제
알라딘은 궁전에서 지루한 삶에 싫증을 느꼈다. 항상 변함없이 똑같은 일과 부인 자스민과 아이들은 알라딘에게 더 이상 큰 흥미를 가져다주지 못했다. 그는, 더 이상 궁전에서 지루한 삶을 살 수 없다고 생각했고 모험을 떠나기로 했다.
알라딘이 살고있는 나라에는 요정이 나타나는 램프가 묻혀있다는 전설이 있다. 이 램프는 지금까지 그 누구도 찾지 못했던 램프이다. 알라딘은 이 램프를 찾기로 했다.
예로부터 내려오는 전설에 의하면 램프는 사막에 묻혀있다. 사막은 N*N 칸이 그리드형태로 배열되어 있는 모습으로 나타낼 수 있다. 행과 열은 위에서 부터 아래로, 왼쪽부터 오른쪽으로 1번부터 N번까지 번호가 매겨져 있다. 어떤 칸에는 마법사가 살고 있고, 마법사는 알라딘에게 가야할 방향을 알려준다.
알라딘은 사막의 가장 왼쪽 위 칸에서 모험을 시작한다. 이 날은 월요일이며, 알라딘은 오른쪽을 보고 있다. 알라딘은 아래 세 단계를 거쳐서 다음 칸으로 이동하게 된다.
- 알라딘이 있는 칸에 마법사가 깨어있다면, 알라딘은 마법사가 말해주는 방향으로 방향을 바꾼다. 이때, 마법사가 말하는 방향은 90도 왼쪽 방향과 오른족 방향 둘 중 하나이다.
- 알라딘이 한 칸 전진했을 때, 사막읙 경계를 벗어난다면, 그는 180도 방향을 바꾼다.
- 알라딘은 한 칸 전진하고, 이것은 정확하게 하루가 걸린다. (1, 2단계에 걸리는 시간은 없다)
모든 마법사가 말해주는 방향은 요일에 따라서 다르고, 길이가 7인 문자열로 나타낼 수 있다. 문자열은 'L', 'R', 'S'로 이루어져 있으며, 각 문자는 어떤 요일에 무슨 방향을 말해주는지를 나타낸다. 첫 번째 문자는 월요일, 두 번째 문자는 화요일, ... 이며, 'L'은 왼쪽으로, 'R'은 오른쪽으로 방향을 바꾸라는 의미이다. 'S'는 그 날은 마법사가 잠을 잔다는 뜻이다.
알라딘은 모험을 떠나기전에 유명한 예언가는 알라딘이 방향을 K번 바꾼다면 (1단계와 2단계) 램프를 발견한다고 말했다. 이 예언대로라면 알라딘은 며칠 만에 램프를 발견하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사막의 크기 N과 예언가의 예언 K가 주어진다. (2 ≤ N ≤ 200, 1 ≤ K ≤ 1,000,000,000)
둘째 줄에는 마법사의 수 M이 주어진다. (0 ≤ M ≤ 10000)
다음 M개 줄에는 마법사의 위치 R, C와 스케쥴을 나타내는 문자열이 주어진다. R은 마법사가 있는 행의 번호, C는 열의 번호이다.
한 칸에 두 명 이상의 마법사가 있는 경우는 없으며, 항상 (1, 1)에는 마법사가 없다.
출력
첫째 줄에 램프를 발견하는데 총 며칠이 걸리는지 출력한다.
예제 입력 1
3 1 0
예제 출력 1
2
예제 입력 2
5 2 2 1 3 RRSRRRR 1 5 RRRRLRR
예제 출력 2
4
예제 입력 3
5 5 3 1 3 SSRSSSS 3 3 SSSLSSS 4 3 SSRSSLS
예제 출력 3
10
출처
Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #5 6번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호