맑은 하늘 프로젝트 문제 질문입니다. oysiya 문제 링크입니다: http://algospot.com/judge/problem/read/CLEARSKYPROJECT 이 문제를 생각해보면서 여러 방향으로 접근 해 보다가 Dynamic하게 접근을 해보았는데요, Greedy로도 풀릴 것 같다는 생각을 하게 되었습니다. 먼저 제가 접근한 Greedy한 방법은 다음과 같은 사실들에 기초합니다: 어떠한 하나의 구름을 제거할 때, 가장 최소의 비용은 i번째 구름의 시작 지점인 Left_i지점에 레이저를 쏘아 i번째 구름 하나만 제거할 때 이다. Left_i순으로 정렬했을 때, i-1번째 구름까지 제거가 되어있다면 Left_i 지점에 레이저를 쏘았을 때에는 i번째 구름 하나만 맞는다.(다른 구름과 Left_i지점을 공유하지 않는다고 할 때) 위의 조건들을 따져보았을 때, Left_i순으로 구름들을 정렬하고 k-1개의 구름을 하나씩 제거(물론, 중복이 있다면 더 많을 수도 있지만)하고 마지막 한 번의 레이저는 남은 구름들을 한 번에 제거할 수 있는 위치 중 가장 비용이 최소화 되는 지점에 레이저를 쏜다면 해결되지 않을까 싶습니다만, 혹시 제가 미처 생각하지 못했던 점이 있는지 궁금해서 질문 글 올립니다. 고수님들의 조언 기다리고 있겠습니다. 12년 전
2개의 댓글이 있습니다. Being 구름이 모두 네 개로 [1, 10], [2, 9], [11, 20], [12, 19] 꼴로 있다고 하면 2와 12에 각각 한 번씩 발사해야 네 개를 모두 제거할 수 있습니다. 말씀하신 전략대로라면 이 경우 구름을 모두 제거하지 못할 것입니다. 12년 전 link oysiya 아! 그래프가 여러 그룹으로 나누어진 경우를 생각하지 못했네요. 감사합니다. 12년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
oysiya
문제 링크입니다:
http://algospot.com/judge/problem/read/CLEARSKYPROJECT
이 문제를 생각해보면서 여러 방향으로 접근 해 보다가 Dynamic하게 접근을 해보았는데요,
Greedy로도 풀릴 것 같다는 생각을 하게 되었습니다.
먼저 제가 접근한 Greedy한 방법은 다음과 같은 사실들에 기초합니다:
어떠한 하나의 구름을 제거할 때, 가장 최소의 비용은 i번째 구름의 시작 지점인 Left_i지점에 레이저를 쏘아 i번째 구름 하나만 제거할 때 이다.
Left_i순으로 정렬했을 때, i-1번째 구름까지 제거가 되어있다면 Left_i 지점에 레이저를 쏘았을 때에는 i번째 구름 하나만 맞는다.(다른 구름과 Left_i지점을 공유하지 않는다고 할 때)
위의 조건들을 따져보았을 때,
Left_i순으로 구름들을 정렬하고 k-1개의 구름을 하나씩 제거(물론, 중복이 있다면 더 많을 수도 있지만)하고
마지막 한 번의 레이저는 남은 구름들을 한 번에 제거할 수 있는 위치 중 가장 비용이 최소화 되는 지점에 레이저를 쏜다면 해결되지 않을까 싶습니다만,
혹시 제가 미처 생각하지 못했던 점이 있는지 궁금해서 질문 글 올립니다.
고수님들의 조언 기다리고 있겠습니다.
12년 전