Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

Posts List


2014년 4월 26일 토요일

[Algospot] 용감한 오리

용감한 오리

문제 ID : BRAVEDUCK
시간제한 : 1000ms
메모리 제한 : 65536kb
제출횟수 : 367
정답횟수 (비율) : 101(27%)
출제자 : Pekaz
출처 : 제 3회 전국 대학생 프로그래밍 대회 동아리 연합 여름 대회

하나의 큐를 이용하면 간단히 해결이 가능하네요.
돌다리의 좌표를 점이라고 한다면.

우선 시작점을 큐에 넣고,

큐에서 선입선출에 따라 하나씩 점들을 빼며
이 점과 연결이 가능한(거리가 최대 점프력 J보다 작은) 점들을 큐에 넣으면 됩니다.

도착점이 큐에 들어간다면 YES.
큐에 더이상 넣을 수 있는 점이 없다면 NO.

여기서는 큐의 용량을 줄이기 위해 처음 점들의 좌표를 저장했던 배열을 이용하여 큐에 넣는 점들을 배열의 앞쪽 점들과 위치를 바꿔가며 진행하였습니다.

Algospot에서 제공하는 테스트 case 의 경우 시작점 보다는 끝점부터 연결해 가는게 좀 더 빠른 결과를 보는 듯 하네요.

200805BRAVEDUCKGOnecpp666B정답4ms1

>>소스보기

댓글 없음:

댓글 쓰기