용감한 오리
문제 ID : BRAVEDUCK시간제한 : 1000ms
메모리 제한 : 65536kb
제출횟수 : 367
정답횟수 (비율) : 101(27%)
출제자 : Pekaz
출처 : 제 3회 전국 대학생 프로그래밍 대회 동아리 연합 여름 대회
하나의 큐를 이용하면 간단히 해결이 가능하네요.
돌다리의 좌표를 점이라고 한다면.
우선 시작점을 큐에 넣고,
큐에서 선입선출에 따라 하나씩 점들을 빼며
이 점과 연결이 가능한(거리가 최대 점프력 J보다 작은) 점들을 큐에 넣으면 됩니다.
도착점이 큐에 들어간다면 YES.
큐에 더이상 넣을 수 있는 점이 없다면 NO.
여기서는 큐의 용량을 줄이기 위해 처음 점들의 좌표를 저장했던 배열을 이용하여 큐에 넣는 점들을 배열의 앞쪽 점들과 위치를 바꿔가며 진행하였습니다.
Algospot에서 제공하는 테스트 case 의 경우 시작점 보다는 끝점부터 연결해 가는게 좀 더 빠른 결과를 보는 듯 하네요.
| 200805 | BRAVEDUCK | GOne | cpp | 666B | 정답 | 4ms | 1 |
>>소스보기
댓글 없음:
댓글 쓰기