그리디

문제 바로가기 > 1202번: 보석도둑 얼핏보면 냅색 알고리즘이여서 DP를 이용해야 할것 같지만 가방에는 최대 한 개의 보석만 넣을 수 있다는 조건이 있다.그리디 알고리즘과 우선순위 큐를 사용하여 풀 수 있는 문제이다. 모든 가방에 대해 모든 보석을 검사하면 위 문제를 해결할 수 있으나, N과 K는 최대 30만이기때문에 O(9 x 10^10)으로 시간 초과가 난다. 따라서 O(N^2)보다 줄이기 위해서 우선순위 큐 자료구조를 이용해야 한다.보석은 무게에 대해 오름차순 정렬하되, 무게가 같을 경우 가격에 대해 내림차순 정렬한다.가방은 오름차순 정렬한다.모든 가방에 대해서 반복문을 수행한다.특정 가방의 무게보다 작은 보석의 가격을 모두 우선순위 큐에 집어넣는다. (이때, 우선순위 큐는 가격에 대해 내림차순 ..

문제 바로 가기 > 백준 2178번 꿀따기  그리디 + 누적합을 이용해 푸는 문제이다. 총 3가지 경우가 있다.벌 - 벌 - 벌통: 벌 1을 맨 왼쪽에 벌통을 맨 오른쪽에 고정 -> 벌 2를 자유롭게 배치벌통 - 벌 - 벌: 벌 1을 맨 오른쪽에 벌통을 맨 왼쪽에 고정 -> 벌 2를 자유롭게 배치벌 - 벌통 - 벌 : 벌을 모두 양 끝쪽에 고정 -> 벌통을 자유롭게 배치이때 각 벌이 지나갈 때 꿀을 먹을 수 있는 양은 누적합으로 계산해야 한다!import java.util.Arrays;import java.util.Scanner;public class _21758 { public static void main(String[] args) { Scanner sc=new Scanner(Sys..