li_la_4   4년 전

국민대 알고리즘 대회 나가신 분들중에 123번 무슨 알고리즘으로 푸셨는지 알려주실 분 있나요?? 

1번은 그냥 브루트포스 같은데 13,14,15가 테케가 까다로웠고..

2번은 그냥 모르겠고...

3번은 가중치 있는 그래프에 탐색?? bfs 돌리면 편할것 같았고..


어떤 알고리즘으로 푸셨는지 설명좀 부탁드려요!!

mythofys   4년 전

1번이 나머지 때려서 브루트포스로 O(n)에 풀리고

2번이 좌표압축(이라기에는 애매한가?), 좌표 다루는 테크닉으로 좌표를 배열에 저장한 다음 마스크 안 낀 사람들의 최대 x,y좌표와 배열의 값을 이용하면 질문 개수와 정점 개수 정도의 시간 복잡도에 풀립니다. O(q+n+m), n,m은 각각 마스크 낀 사람들의 좌표 개수, 안 낀 사람들의 좌표 개수입니다. q는 질문한 구역 개수 입니다.

3번은 bfs+vector(간선 저장)이나 bfs+배열+이분탐색으로 풀려요. 안해봐서 모르겠지만, 이분탐색을 안써도 뚫릴 것 같긴 했어요. 이차원 벡터 페어가 나오는데 무서워도 데이크스트라(다익스트라) 하실 때처럼 그냥 푸시면 됩니다.


+혹시 문제 유출에 위험한 부분 있으면 글 삭제하거나 수정할게요. 답글 달아주세요.

li_la_4   4년 전

고맙습니다..!! 

덕분에 다시 정리할 수 있겠네요 

이정도는 유출걱정은 안하셔도 될 것 같아요 ~~ 고맙습니다 

li_la_4   4년 전

혹시 백준에 비슷한 문제 있을까요..? 

정리하는데 도움이 될 것 같아서요!!

댓글을 작성하려면 로그인해야 합니다.