240411 백준(BOJ) 24041 성싶당 밀키트(Python) 이분 탐색 문제. 현재 날짜에 따라 세균수를 체크해야 하는데, 날짜는 최대 2e9까지 가능하므로 O(logn)으로 값을 탐색해야 할 것이라고 판단했고, "특정 조건을 만족하는 범위 내의 최댓값"을 구해야 하므로 이분 탐색을 사용해야함이 자명하다고 생각했다. 이때 각 날짜에 맞는 세균수를 구해야 하는데, 가장 먼저 k개의 중요하지 않은 재료를 빼야했다. 그리디하게 생각해보면 당연히 k번의 횟수를 모두 소모해야하는데, 중요하지 않은 재료가 k개 이상인 경우에는 현재 날짜를 기준으로 가장 세균수가 큰 재료들부터 빼줘야한다. 따라서 이분 탐색을 한 번 진행할 때마다 중요하지 않은 재료들을 현재 세균수를 기준으로 내림차순 정렬한 뒤, 그 중 순서대로 k개를 제외한 나머지 재료들의 세균수를 모두 더했다. 그 후에는.. 2023. 4. 18. 이전 1 다음