핵어렵다 ㅎㅎ https://www.acmicpc.net/problem/5474 1. Greedy - O(NHlgH)그리디 전략을 설명하기 전에 사실 돛대의 순서들이 문제에 전혀 상관이 없다는 사실을 알아야 한다. 때문에 돛들을 편한대로 정렬한 다음에 쓰면 된다.그리디 전략은 다음과 같다. 돛대라는 말은 어감이 짜증나니(?) 막대라는 말로 대신하겠다." 막대들을 길이가 증가하는 순서대로 정렬한 후, 각 막대에 대해서 H개의 돛들을 꽂을 수 있는 열 중 가장 꽃혀있는 돛이 적은 열에 꽃는다. 이를 모든 돛에 대해서 반복한다. 이후 열에 꽃혀있는 돛의 개수가 n개일 경우 n * (n-1) / 2를 각 열에 대해서 더한다." 딱 봐도 될거같은 이 그리디 전략은 실제로 된다. (^^;) 왜 되는지는 나도 모르니..
tl;dr 우여곡절이 많았는데 생각보다 많이 올라서 기분좋다 (+85 = 2057) A패스 여담으로 코드를 개더럽게 짰다 (나만 더럽게 짠건 아닌듯 ㅎㅎ) B그래프를 이것저것 그려보며 생각을 해봤다 사실 처음에는 Hopcroft Karp가 아닐까 하는 알지도 못하는 알고리즘에 대한 개쓸데없는 생각을 하면서 멘붕을 시전했지만 역시 개쓸데없는 생각이었고 그냥 위상정렬하면 되더라.. http://183.106.113.109/pool/ioi_islands/ioi_islands.php… 를 얼마전에 푼게 엄청 도움된듯. 여러분도 푸세여! 디버깅하는데 시간을 꽤 날렸는데 너무 아깝다 Dynamic Scoring 상에서 500점이라서 멘붕했었는데 시스템에서 1000돼서 행복했다. 다행이도 시스템 테스트에서 사람들이 ..
- Total
- 407,305
- Today
- 114
- Yesterday
- 546