그리디

문제 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 방법 멀티탭 구멍의 개수 N과 전기용품의 총 사용 횟수 K가 주어진다. 그 뒤 사용 순서대로 K 이하의 수가 K만큼 주어진다. 쉽게 말해서 두 번째 줄 i번째 입력의 값은 i에 사용하는 기기라는 뜻이다. 페이지 교체 알고리즘이 떠오르는 문제이며, 교체 횟수가 최소가 되는 알고리즘은 바로 가장 오랫동안 사용되지 않는 페이지를 교체하는 최적(Optimal) 알고리즘이다. 다만 실제로는 앞으..
문제 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 풀이 방법 센서를 점으로 보면 다음과 같이 해석된다. 일직선상에 N개의 점이 있을 때 이들을 다 포함하는 길이의 합이 최소가 되는 K개의 선분을 만든다. 선분 사이의 K-1개의 공간이 생기게 되는데, 이 공간들을 가장 크게하면 선분 길이 합이 최소가 된다. 점들을 오름차순으로 정렬한다. 인접한 점들 간 거리(선분 길이)를 내림차순으로 정렬한다. 인접한 점들 간 거리를..
virtus
'그리디' 태그의 글 목록