5개의 댓글이 있습니다.
-
-
JongMan -
http://algospot.com/aoj/problems/read/DARPA 이것도 한번 보삼 ㅎㅎ
13년 전 link
-
-
-
김우현 -
http://uva.onlinejudge.org/external/119/11920.html
알고리즘 생각해 보셨으면 위 문제도 풀어 보시면 좋을 것 같습니다!
13년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
룡이
도움만 받는 것 같지만, 여기만한 곳이 없어서 질문 드립니다.
이런 문제를 가지고 고민하고 있는데요. 문제 형식으로 적어볼게요.
당신은 장거리 달리기 대회를 주관하는 스태프이다.
장거리 달리기는 출발점부터 도착지점까지 일직선을 참가자들이 달리는 경기이다.
참가자들을 위해 코스 중간중간에 물을 두는데, 물을 잘 배치했는지의 점수는 물이 없는 구간의 최대거리이다.
대회측은 알바생들을 시켜 하루 전날 물을 배치했는데 알바생들은 규칙없이 아무렇게나 물을 배치했다.
남은 물 N 박스가 있을 때 물이 없는 구간(구간 단위는 정수)의 최대거리를 최소화하시오.
제가 푼 방식을 적어보면 이런 Array 가 있는데요.
주어진 N 은 3 이라고 하구요. O 는 물이 놓여진 곳, X 는 물이 없는 곳입니다.
OOXXXXOXOXOOXXXXXXOOXXXXOXXX
그럼 이 상태에서 물이 없는 구간의 거리는 4, 1, 1, 6, 4, 3 이 됩니다.
푸는 방법은 제일 긴 구간인 6 에다 물을 하나 두고 (6 -> 3 2),
그 다음 긴 구간이 4 에 물을 한 개씩 둡니다 (4 -> 2 1).
구현으로 세가지 방법을 써 봤는데 셋 다 고만고만하고 만족스럽지 못한 런타임이 나와서요. (v 는 Vector 입니다.)
(1) 매번 v 를 소팅한 후 첫번째 원소를 꺼내 반으로 나눈 뒤 중간지점에 물을 놓고 반으로 나눈 두개를 다시 v 에 넣는다.
ex) 6 4 4 3 1 1 -> 6을 꺼내 하나 빼고 3 2로 다시 v에 넣고 소팅 -> 4 4 3 2 1 1
(2) PriorityQueue 클래스를 써서 Top 을 꺼내 반으로 나눈 뒤 나눈 두개를 다시 Queue 에 넣는다.
(3) 처음에 한 번만 소팅한 후, 매번 첫번째 원소를 꺼내 반으로 나눈 뒤 v 를 앞에서부터 Linear Search 하며 다시 넣는다.
매번 한 단계씩 수행하지 않고,
초기 단계만 보고 N 개의 물을 각각 몇번째 구간에 몇개씩 두자 !
라고 찾는 방법이 있을까요 ?
13년 전