프로그래밍/백준 복기31 [이분탐색] BOJ 2512: 예산 https://www.acmicpc.net/problem/2512 예산 내에서 지자체가 요구한 예산들 다 커버할 수 있으면 지자체 중 요구한 예산이 가장 큰 지자체의 예산을, 그렇지 않으면 특정 상한선을 정해서 그 위로는 자르고, 전체 예산안을 만족할 수 있는 상한선 중 가장 큰 값을 반환하면 된다. 전자는 그냥 전체 요구 예산의 합이 예산 한도보다 낮으면 최대값을 반환하면 될 것이고, 후자 쪽이 binary search를 통해 상한선의 최대값을 찾아야 하는 문제이다. #include #include #include using namespace std;int answer;void findMaximum(vector &budget, int min, int max, int maxBudget){ if(mi.. 2024. 11. 6. [Greedy] 백준 4796: 캠핑 https://www.acmicpc.net/problem/4796 예전에 설탕 문제 풀었던 것을 기억하자. https://gaebaldosamoodosa.tistory.com/79 연속된 P일 중 L일만 사용 가능하다는 것을 일종의 큰 상자로 생각하자. 요컨대 박스 무게는 P이고 안에 포장 빼고 실제 내용물이 L 들어 있는 것이다. 그리고 남는 여분은 작은 상자로 포장된다고 생각하자. 큰 상자를 고르는 것이 다른 상자의 선택에 영향을 미치지 않고, 매 순간 가능하다면 작은 상자 대신 큰 상자를 선택하는 것이 결국 가장 많은 내용물을 가져가는 결과를 도출할 것이다. 다시 말해 한 단계의 선택의 다음 단계의 선택에 영향을 미치지 않고, 매 순간 최적의 해가 문제 전체의 최적의 해가 될 것이기 때문에 Gree.. 2024. 10. 23. [이분 탐색] 백준 2805: 나무 자르기 https://www.acmicpc.net/problem/2805 이분 탐색의 기본을 사용하는 문제이다. 먼저, 절단기 높이의 최소값은 0이고, 최대값은 나무들 중 가장 높은 나무의 높이이다. 따라서 초기에 min = 0, max = max(tree) 라고 하자. 우리가 구해야 할 것은 "원하는 만큼 나무를 가져갈 수 있는 절단기의 최대 높이" 이다. 따라서 절단기 높이에 따라 구할 수 있는 나무의 양이 요구치보다 적을 때는 절대 정답이 될 수 없되 절단기를 더 낮추어야 하므로, max = mid-1로 설정하고 다시 이분탐색을 진행한다. 반면 절단기 높이에 따라 구할 수 있는 나무의 양이 요구치보다 많을 때는 정답이 될 수 있되 절단기를 더 높여서도 해당하는 만큼의 나무를 구할 수 있는지 알아봐야 한다... 2024. 10. 22. [Simulation] 백준 14719: 빗물 14719번: 빗물 (acmicpc.net) 처음에는 각 column 간의 차이를 위주로 접근하다가, 위에서부터 한 row씩 훑고 내려오면서 연산하는 방식으로 접근을 달리했다. 맨 위 row 부터 순회하면서, 만일 값이 1인 칸을 이미 만난 상태라면 이후 0인 칸을 만날 때마다 값을 더해준다. 만일 다시 값이 1인 칸을 만나면, 해당 값을 정답에 더해주고 0으로 초기화한다. 양 옆이 뚫려 있다고 생각해야 하므로, 다음 row로 내려갈 때 값을 0으로 초기화한다. 이 때 1인 칸을 만났는지 여부를 확인하는 flag(여기서는 isFill)을 false로 초기화 해 준다.#include #include using namespace std;int main(){ ios_base::sync_with_stdio.. 2024. 6. 8. 이전 1 2 3 4 ··· 8 다음