밤이 블로그

BOJ#6195 Fence Repair * 문제https://www.acmicpc.net/problem/6195 (Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO November 2006 Contest > Gold 1번) * 풀이 최초 생각한 알고리즘은 가장 긴 널빤지를 가장 빨리 만드는 것이었습니다.(늦게 처리할 수록 큰 값이 Cost에 포함되기 때문에) 그러나, 위 알고리즘의 반례는 아래와 같습니다. ex) 5 / 1, 2, 3, 4, 5 일 때 1단계 : 15 -> 5, 10 (15)2단계 : 10 -> 4, 6 (10)3단계 : 6 -> 3, 3 (6)4단계 : 3 -> 2, 1 (3) Cost : 34 1단계 : 15 -> 7, 8 (..

BOJ#7676 Saruman's Army * 문제https://www.acmicpc.net/problem/7676 (University > Stanford Local ACM Programming Contest > SLPC 2006 1번) * 풀이 palantir를 가장 적게 배치하는 것이 목적이다.문제에서 주어진 R은 반경이다.(반지름) 1. palantir 범위에 포함되지 않은 가장 왼쪽 점을 포함하는 가장 오른쪽 점을 구하자. (두 점이 같을 수도 있다.)2. 구한 오른쪽 점이 palantir 위치이다.3. palantir 위치를 기준으로 palantir 범위에 포함되지 않은 가장 오른쪽 점을 구하자. 위 알고리즘을 모든 점이 palantir 범위에 포함될 때까지 반복한다. , 풀이는 위와 같고,중..