그리디

문제 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 풀이 그리디, 정렬, 우선순위 큐 ✔ 정답 코드 1 연료가 높은 주유소가 top에 위치하도록 우선순위 큐에 넣는다. 우선순위 큐를 top에서 부터 방문하며, top이 현재 방문할 수 없는 주유소라면 벡터에 넣는다. 현재 방문할 수 있는 주유소가 top에 위치하였을 때, P에 더하고 벡터에 있는 값들을 다시 우선순위 큐에 넣는다. 이를 P가 L 이상일 때까지 반복 이렇게 하면 다음 방문할 주유소를 탐색할 때, 우선순위 큐..

문제 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 풀이 그리디, 우선순위 큐 [백준][C++] 2109: 순회강연 문제 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불 kantatatam.tistory.com 위의 문제와 같지만 이 문제가 N이 더 크기때문에, 같은 풀이로는 시간 초과가 발생하였다. 각 날짜 별로 풀 수 있는 문제..

문제 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 풀이 그리디, 우선순위 큐 강연료를 최대로 받기 위해서는, 강연료가 크면서 기간이 많이 남은 강연은 최대한 나중에 하고, 기간이 짧은 강연을 빠른 날짜에 해야 한다. 우선순위 큐를 이용해서, 강연료가 크면서 남은 기간이 오래 남은 강연 순서로 탐색한다. 현재 탐색 중인 강연을 최대한 나중으로 미뤄서 실행하면 기간이 얼마 남지 않으면서 강연료가 큰 강연을 앞에 날짜에 실행할 수 있다. // 강연료가 크면서, 남은 기간이 오..

문제 19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의 www.acmicpc.net 풀이 그리디, 우선순위 큐 [백준][C++] 11000: 강의실 배정 문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 그리디, 우선순위 큐 [백준][C++] 2170: 선 긋기 문제 풀 kantatatam.tistory.com 위의 문제와 풀이가 같은 문제 코드 #include #include ..

문제 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 풀이 그리디, 우선순위 큐 가장 작은 수를 만들기 위해서는 뽑는 카드가 현재 상태에서 가장 작은 2장의 카드를 뽑아야 한다(그리디). 현재 상태에서 가장 작은 카드를 뽑기 위해 우선순위 큐를 사용한다. 우선순위 큐의 탑에 있는 카드를 2장 뽑는다. 2장의 카드를 더한 값을 우선순위 큐에 2번 더한다. 이를 m번 반복한다. 여기서 카드의 수가 크기때문에 자료형은 long long을 사용해야 한다. 코드 #include #i..

문제

문제 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 풀이 그리디, 정렬 구멍이 정렬되어 들어오지 않으므로 정렬이 필수이다. // 정렬 필수 sort(hole.begin(), hole.end()); 구멍 start에서 테이프를 붙였을 때, 막을 수 있는 구멍의 거리는 start + L - 1까지이다. 이 거리보다 먼 구멍은 막을 수 없으므로, 새로운 테이프를 사용해야 한다. start + L - 1에서 다음 구멍 까지는 테이프를 붙이지 않아도 되므로, 다음 구멍이 start가 되어 다시 sta..

문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 그리디, 우선순위 큐 [백준][C++] 2170: 선 긋기 문제 풀이 정렬, 스위핑 문제이다. 현재 긋고 있는 선의 시작을 start, 끝을 end라고 하자. 선을 긋고 있을 때, 어떤 상황에서 다음 선을 한번에 그을 수 있을까? 만약 다음으로 그을 선의 시작이 end kantatatam.tistory.com 위의 문제가 생각나는 문제이다. A강의와 B강의가 서로 같은 강의실을 사용하려면 A강의가 B강의의 시작하는 시간보다 빨리 끝나야 한다. 오름차순 우선순위 큐를 만든다. priority_queue..

문제 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 그리디, 자료 구조, 우선순위 큐 2가지 방법으로 문제를 풀 수 있다. 1. 가방을 오름차순으로 정렬하고, 현재 가방에 넣을 수 있는 가격이 최대인 보석을 찾는 방법 보석과 가방을 오름차순으로 정렬한다. 용량이 적은 가방부터 현재 가방에 들어갈 수 있는 보석을 모두 우선순위 큐에 넣는다. 그렇게 되면, 우선순위 큐의 top에는 현재 가방에 들어갈 수 있으면서 가격이 최대인 보석이 위치하게 된..

문제 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 풀이 그리디 n이 5로 나누어 떨어진다면 5원으로 거스름돈을 채울 수 있다. 5로 나누어 떨어지지 않는다면 2원과 같이 채워야 한다. 1원이 아니라 2원이기 때문에, 5로 나눈 나머지를 2원으로 맞춰서 낼 수 없다. 예를 들어 1원 혹은 3원이 남았다면 2원으로 채울 수 없다. n이 5로 나누어 떨어지지 않는다면, n이 5로 나누어 떨어지거나 n이 0 이하가 될 때까지 2씩 차감한다. n이 0미만이 된다면, 거슬러 줄 수 없는 경우이다. 코드 #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin..