greedy 6

BOJ#1946 신입 사원

BOJ#1946 신입 사원 * 문제https://www.acmicpc.net/problem/1946 * 풀이서류 성적으로 오름차순 정렬 후 면접 성적을 순차적으로 검사한다. 정렬 이후 첫번째 줄은 무조건 합격이므로2번째 줄부터 N번째 줄까지 순차적으로 진행한다. 서류 성적으로 한번 정렬 되었으므로 이미 누군가에게는 한번 졌다는 뜻이다.따라서 면접 성적에서 누구에게라도 한번만 더 지게 되면 탈락이다. 따라서, 2번째 줄부터 N번째 줄까지 순차적으로 진행하면서면접 성적의 최고 순위를 계속 갱신 + 최고 순위와 현재 라인을 검사 * 나의 코드 https://github.com/stack07142/BOJ/tree/master/BOJ%231946_Freshman/src import java.io.IOExcepti..

Algorithm/Greedy 2017.03.22

BOJ#6195 Fence Repair

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 (..

Algorithm/Greedy 2017.02.02

BOJ#7676 Saruman's Army

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 범위에 포함될 때까지 반복한다. , 풀이는 위와 같고,중..

Algorithm/Greedy 2017.02.02

POJ#3617 Best Cow Line

POJ#3617 Best Cow Line * 문제http://poj.org/problem?id=3617 * 풀이 1.처음 문자와 마지막 문자가 크거나 작은 경우 뿐만 아니라두 문자가 같은 경우도 잘 생각해보아야 한다. 예) GFABFG 2. 문자 수가 80이 될 때마다 new line을 삽입해야 한다.여기서 String의 length를 이용하지 말고 (\n이 length에 포함되므로)loop 횟수를 이용해야 한다. * 나의 코드https://github.com/stack07142/HappyAlgo/tree/master/HappyAlgo%238_BestCowLine/src import java.io.BufferedReader; import java.io.IOException; import java.io.I..

Algorithm/Greedy 2017.02.01

BOJ#1700 멀티탭 스케쥴링

BOJ#1700 멀티탭 스케쥴링 * 문제https://www.acmicpc.net/problem/1700 * 풀이 전기용품 사용 순서가 주어지므로,이를 통해 멀티탭에서 어떤 플러그를 뽑아야 하는지 판단할 수 있다. -> 현재 멀티탭에 꽂혀있는 전기용품 중 가장 나중에 사용되는 전기용품의 플러그를 뽑는다. * 테스트 케이스 2 72 3 2 3 1 2 7 : 2 2 132 3 1 3 1 3 1 3 2 2 2 2 2 : 2 2 153 2 1 2 1 2 1 2 1 3 3 3 3 3 3 : 2 3 81 2 3 4 1 1 1 2 : 1 1 31 2 1 : 2 3 61 2 3 4 1 2 : 1 6 71 1 1 1 1 1 2 : 0 2 101 2 3 2 3 2 2 2 1 2 : 2 5 201 2 3 4 1 1 1 3 ..

Algorithm/Greedy 2017.02.01

BOJ#3109 빵집 (PLINOVOD)

BOJ#3109 빵집 (PLINOVOD) * 문제https://www.acmicpc.net/problem/3109 * 풀이 1) 가스관과 빵집을 연결하는 가스 파이프 라인은 첫번째 열에서 시작하고, 마지막 열에서 끝나게 됩니다. 2) 첫번째 열과 마지막 열은 항상 비어있습니다.3) 각 칸은 3가지 방향으로 (↗️, ➡️, ↘️) 연결할 수 있습니다.4) 건물이 있을 경우 파이프를 설치할 수 없고, 파이프끼리 겹칠 수도 없습니다. 1번 조건 : 첫번째 열에서 시작하여 마지막 열까지 진행 후 return 되는 Backtracking 함수 구현 : 마지막 열 도달 시 1을 return하여 파이프라인 개수를 증가시킨다. 2번, 3번 조건 : 첫번째 열은 모든 행을 검사해야 하고, 그 다음부터는 최대 3개의 행만..

Algorithm/Greedy 2016.12.30