야생가오리

https://www.acmicpc.net/problem/1052 용량 제한은 없고, 처음 상태에는 물 1리터가 들어있는 물병 N개한번에 옮길 수 있는 물병은 K개하고자 하는 것: 물을 재분배(같은 양의 물병 2개를 한쪽에 몰아넣음)해, 비어있지 않은 물병이 K개를 넘지 않도록 만들기 (찬 물병이 K개 이하가 되게)이걸 위해 새 물병(1리터가 들어있음)을 구매할 수 있음 ex) N=3, K=1이면물병 3개, 한번에 1개밖에 옮길 수 없다면1 1 1이 상태에서 재분배를 해도2 0 1 이 되므로 비어있지 않은 물병이 1개 이하가 될 수는 없다. 이때 물병 1개를 산다면, 물병이 4개가 되므로2 0 1 1이렇게 들어있을거고2 0 2 0이래되고4 0 0 0최종적으로 이렇게 될 수 있으므로 비어있지 않은 물병이 ..

https://www.acmicpc.net/problem/11399 최소 시간(전체)이 되도록 순서를 정하라는데전체 기다리는 시간이 줄어들려면 그냥 빨리끝나는 사람부터 뽑으면 된다.매 상황마다 가장 빨리 끝날 수 있는 사람을 뽑아나가면 그게 곧 최소시간이 된다.= 그리디를 써라#include #include #include using namespace std;int main(){ int n; cin >> n; vector arr(n); for(int i=0;i> arr[i]; } sort(arr.begin(), arr.end()); int answer = 0; for(int i=0;i

https://www.acmicpc.net/problem/1931 그리디매 단계에서 최적의 방법을 선택하는 알고리즘. 탐욕법이라고도 한다항상 최적해를 찾을 수는 없다. 사용 조건은-시간/공간적 제약으로 최적해를 구하지 못해 근사해를 구해야 하는 문제-그리디를 사용해도 항상 최적해를 구할 수 있는 문제여야 한다.두번째 경우로는1) 탐욕 선택 속성: 탐욕적으로 선택하더라도 문제의 최적해가 보장될 때2) 최적 부분 구조: 부분문제의 최적해가 전체 문제의 최적해로 확장될 수 있을 때가 있다. 이 문제는 그리디를 사용할 수 있는 문제다.가장 빨리 끝나는 회의를 선택하면 다른 회의에 사용할 수 있는 시간이 많아지고,매번 가장 빨리 끝나는 회의를 선택한다면 남은 회의 시간에 대해 똑같이 가장 빨리 끝나는 회의를 선택..