보노보노 힌트좀..얻을수 있을까요 ^^;; ibis 안녕하세요 열심히 알고리즘 문제 풀고있는 학생입니다. 많이 생각해봤지만 계속 TLE가 나와서..ㅠㅠ 염치를 불구하고 힌트좀 얻어보고 싶어요 문제 : http://algospot.com/judge/problem/read/CAVEMAN A.....B.....CD..........이런씩으로 아이들이 있을때 왼쪽(A)에 닿을 수 있는 불크기가 가장큰 B를 찾아서 그 크기 만큼C를 찾아 지우고요 C다음에 있는 D에 대해서도 똑같이 불빛이 닿을 수 있는 가장 큰 녀석을 찾는 씩으로 했습니다. 근데 20만 해달들이 있을때 다 1의 크기를 갖고 있어버리면 n^2이..돼서 TLE가 되고 있는거 같습니다. 좀더 개선할 수 있는 방향이 뭘까요?;; 12년 전
7개의 댓글이 있습니다. VOCList 말씀하신 방법이 맞습니다. 현재 불이 닿지 않는 가장 왼쪽에 있는 아이를 기준으로 이 아이를 가장 멀리서 비출 수 있는 등불을 계속 찾아 나가시면 됩니다. 주어진 데이터를 조금 가공해서 생각해보시면 가장 멀리있는 등불을 찾아가는 시간을 오더 n보다 빠르게 개선 할 수 있는데요. 고민해보세요~ 12년 전 link VOCList 답은 그래도 안풀리시면 다음에 공개 ㅜㅜ 12년 전 link Being 염치불구하실 건 없습니다! :) 질문이 얼마나 반가운지.. 흑흑.. VOCList님 말씀대로 전략은 맞는데, 약간 방향을 틀고 자료 구조를 잘 설계하시면 될 것 같습니다. 12년 전 link ibis 답변 감사드립니다 ㅎㅎ 조금더 고민해볼께요 12년 전 link ibis ㅠㅠ...흑 힌트 조금더 부탁드릴께요... 12년 전 link ibis ^^ 해결했습니다~ 12년 전 link VOCList ! >_< 12년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
ibis
안녕하세요 열심히 알고리즘 문제 풀고있는 학생입니다.
많이 생각해봤지만 계속 TLE가 나와서..ㅠㅠ 염치를 불구하고
힌트좀 얻어보고 싶어요
문제 :
http://algospot.com/judge/problem/read/CAVEMAN
A.....B.....CD..........이런씩으로 아이들이 있을때
왼쪽(A)에 닿을 수 있는 불크기가 가장큰 B를 찾아서 그 크기 만큼C를 찾아 지우고요
C다음에 있는 D에 대해서도 똑같이 불빛이 닿을 수 있는 가장 큰 녀석을 찾는
씩으로 했습니다.
근데 20만 해달들이 있을때 다 1의 크기를 갖고 있어버리면
n^2이..돼서 TLE가 되고 있는거 같습니다.
좀더 개선할 수 있는 방향이 뭘까요?;;
12년 전