https://www.acmicpc.net/problem/2519 새로운건 없는데 다까먹었네.. 다음과 같은 논리식들을 만족하는 막대기가 필요하다.1. 교차하는 막대기 두 쌍이 있다면, 두 쌍 중 한 쌍이 사라져야만 한다.2. 3개의 막대기 중 한 막대기를 사용한다면, 나머지 두 막대기는 사용하면 안된다.고로 2-SAT으로 풀리는 문제이다. 논리식을 만들어주자. 2번은 너무 당연히도 명제이다. 막대기 A를 지운다는 것을 E(A) 라고 표현했을 때, 2번은 E(A) -> ~E(B), E(A) -> ~E(C)... 를 6 (3 * 2)개 만들어주면 된다.1번은 약간 변형해줘야 명제가 된다. E(A) || E(B) 라는 식의 명제인데. 논리식은 가정이 참이면 결론이 참이어야 하고, 가정이 거짓이면 항상 참이다..
핵어렵다 ㅎㅎ https://www.acmicpc.net/problem/5474 1. Greedy - O(NHlgH)그리디 전략을 설명하기 전에 사실 돛대의 순서들이 문제에 전혀 상관이 없다는 사실을 알아야 한다. 때문에 돛들을 편한대로 정렬한 다음에 쓰면 된다.그리디 전략은 다음과 같다. 돛대라는 말은 어감이 짜증나니(?) 막대라는 말로 대신하겠다." 막대들을 길이가 증가하는 순서대로 정렬한 후, 각 막대에 대해서 H개의 돛들을 꽂을 수 있는 열 중 가장 꽃혀있는 돛이 적은 열에 꽃는다. 이를 모든 돛에 대해서 반복한다. 이후 열에 꽃혀있는 돛의 개수가 n개일 경우 n * (n-1) / 2를 각 열에 대해서 더한다." 딱 봐도 될거같은 이 그리디 전략은 실제로 된다. (^^;) 왜 되는지는 나도 모르니..
- Total
- Today
- Yesterday