[Codeforces 1110B] Tape 요즘 그리디문제를 자꾸 바이너리 서치로 풀려고 삽질하는 것 같다. 그리디 문제는 솔루션이 그리디라는 것만 알면 쉬운데, 확신이 없어서 헤매는 것 같다. 길이가 m인 긴 막대에 n개의 부서진 부분이 존재한다. 이 부서진 부분을 붙이기 위해 총 k개의 테이프를 사용할 수 있을 때(한 개당 테이프 길이는 상관없음) 필요한 총 테이프 길이의 최소는 얼마인지를 묻는 문제이다. 문제는 보기에는 바이너리 서치의 lower bound로 풀면 될 것 같은데 WA를 받았다. 아마 반례가 존재하는 모양인데 아직 정확히 왜 안되는지는 모르겠다. 아무튼 더 확실한 그리디 풀이법이 있으니 그리디로 풀자.사실 이 문제를 간단하게 표현하자면 n개의 인접한 수를 k개의 그룹으로 묶을 때 그룹..
[Codeforces 1070D] Garbage Disposal n일 동안 매일 a_i만큼의 쓰레기가 발생하고(0이면 발생 안함) 그 쓰레기를 크기가 k인 봉투에 담아서 버려야하는데, 오늘 발생한 쓰레기는 반드시 오늘 아니면 내일 안에 처리해야 한다. 이때 필요한 쓰레기 봉투의 최소 개수를 구하는 문제이다. 문제를 처음 풀 때는 맞왜틀을 외치다가 테스트케이스를 슬쩍 봤는데 내가 고려하지 않은 것이 있었다. 내 솔루션은 오늘과 내일의 쓰레기 양을 더한 값을 k로 나눠서 나머지에 따라서 ans를 계산했는데, 이 논리는 오늘 쓰레기가 내일까지 처리되지 않을 수도 있었다. 문제 제약조건상 오늘 쓰레기는 늦어도 내일까지 처리해야하기 때문에 내가 푼 솔루션은 잘못된 것이다. 그래서 올바른 솔루션은 오늘의 쓰레기 양..
[Codeforces 1084B] Kvass and the Fair Nut N개의 음료수의 용량(v_i)과 s가 주어진다. 각각의 음료수에서는 최소 0부터 최대 (v_i)까지 음료수를 빼낼 수 있다. 이렇게 음료는 빼내서 s가 되도록 만들어야 한다. 이때 가장 적게 든 음료수의 용량이 최대가 되도록 하는 문제이다.처음 딱 봤을 때는 당연히 바이너리 서치로 푸는 문제 인 줄 알았다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include#includeusing namespace std;typedef long long ll;int fMax(ll a,ll b){ return a>b?a..