매개 변수 탐색 (6) 썸네일형 리스트형 백준 15573번 [채굴](C++) -yes6686- 티스토리 백준 문제 풀이: 15573 (채굴)문제 링크: https://www.acmicpc.net/problem/15573문제 설명:지하 자원이 묻혀 있는 n×m 크기의 격자에서, 각 칸은 채굴에 필요한 비용이 정해져 있습니다. 채굴은 외곽(맨 윗줄, 맨 왼쪽 열, 맨 오른쪽 열)에 있는 칸들에서 시작해, 4방향(상하좌우)으로만 인접한 칸으로 확장할 수 있습니다. 이때 k개의 칸을 선택해 채굴할 때, 선택된 칸들 중 가장 높은 비용이 최소가 되도록 해야 합니다. 즉, k개의 칸을 채굴할 때 필요한 비용의 최대값을 최소로 만드는 것이 목표입니다.핵심 알고리즘: 다익스트라 스타일의 BFS를 이용한 최소 힙 기반의 탐색. 가장 작은 비용의 칸부터 k개까지 채굴하며, 그 중 가장 마지막 채굴 칸의 비용이 정답이 됩니다.. 백준 2343번 [기타 레슨](C++) -yes6686- 티스토리 백준 문제 풀이: 2343 [기타 레슨]문제 링크: https://www.acmicpc.net/problem/2343문제 설명:길이가 n인 강의 목록이 주어졌을 때, m개의 블루레이에 강의를 나누어 저장하려고 합니다. 이때, 블루레이의 크기가 최소가 되도록 해야 합니다. 블루레이의 크기는 각 블루레이에 들어가는 강의 길이 중 최댓값으로 결정됩니다.즉, 최소한의 블루레이 크기를 이분 탐색을 사용하여 구하는 문제입니다.문제 해결 코드#include #include using namespace std;int arr[100001];int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; int s.. 백준 2110번 [공유기 설치](C++) -yes6686- 티스토리 백준 문제 풀이: 2110 [공유기 설치]문제 링크: https://www.acmicpc.net/problem/2110문제 설명:각각의 집이 일직선 상에 주어졌을 때, k개의 공유기를 설치하여 인접한 공유기 사이의 거리 중 최솟값을 최대로 만드는 문제입니다.즉, 가장 가까운 두 공유기 사이의 거리를 최대로 확보하는 것이 목표이며, 이를 위해 이분 탐색을 사용하여 최적의 간격을 찾습니다.문제 해결 코드#include #include using namespace std;int arr[200001];int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, k; cin >> n >> k; // 집 위치 입력 for (int.. 백준 16401번 [과자 나눠주기](C++) -yes6686- 티스토리 백준 문제 풀이: 16401 (과자 나눠주기)문제 링크: https://www.acmicpc.net/problem/16401문제 설명:과자의 길이가 서로 다를 때, **최대한 길이가 긴 과자**를 만들어 M명의 조카에게 나눠줘야 합니다. 조카에게 나눠줄 수 있는 과자의 길이는 모두 동일해야 하며, 과자를 자를 수 있지만 남는 부분은 버려야 합니다. 이때, 과자의 길이의 **최댓값**을 구하는 문제입니다.문제 해결 코드#include using namespace std;int arr[1000001]; // 과자의 길이를 저장하는 배열int main() { ios::sync_with_stdio(false); cin.tie(NULL); int m, n; // m: 조카 수, n: 과자의 개수 .. 백준 2512번 [예산](C++) -yes6686- 티스토리 백준 문제 풀이: 2512 (예산)문제 링크: https://www.acmicpc.net/problem/2512문제 설명:각 지방에서 요청한 예산의 합이 국가 예산 총액을 초과할 경우, **상한선**을 정해 각 지방의 예산을 조정하는 문제입니다. 예산이 상한선 이하인 경우는 요청한 예산을 그대로 배정하고, 상한선을 초과하면 상한선만큼만 배정합니다. 상한선의 **최댓값**을 구하는 문제입니다.문제 해결 코드#include #include using namespace std;int arr[10001];int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; // 지방의 수 cin >> n; int sum = 0; for.. 백준 1654번 [랜선 자르기](C++)-yes6686- 티스토리 백준 문제 풀이: 1654 [랜선 자르기]문제 링크: https://www.acmicpc.net/problem/1654문제 설명:길이가 각각 다른 K개의 랜선을 최소한 N개의 같은 길이로 잘라야 합니다. 만들 수 있는 최대 랜선의 길이를 구하는 문제입니다.문제 해결 코드#include #include using namespace std;long long int arr[10001];int main() { int k, n; cin >> k >> n; int max = -1; for (int i = 0; i > arr[i]; if (max 코드 설명핵심 아이디어: 이분 탐색을 활용하여 가능한 랜선의 최대 길이를 효율적으로 탐색합니다.구현 세부사항:start: 이분 탐색의 시작.. 이전 1 다음
