이분 탐색 (19) 썸네일형 리스트형 백준 3151번 [합이 0](C++) -yes6686- 티스토리 백준 문제 풀이: 3151 (합이 0)문제 링크: https://www.acmicpc.net/problem/3151문제 설명:정보올림피아드 캠프에서 학생 n명의 실력이 주어진다. 이 중 서로 다른 3명을 뽑았을 때, 실력의 합이 0이 되는 조합의 개수를 구하는 문제이다. 중복 없이 3명을 선택해야 하며, 정렬된 상태를 활용하여 효율적으로 계산할 수 있어야 한다.핵심 알고리즘: 정렬 + 이분 탐색을 활용한 투포인터 기반 조합 탐색. O(n2 log n)문제 해결 코드// 정렬 + 이분 탐색으로 3개의 합이 0인 경우의 수 계산#include #include #include using namespace std;vector v;int main() { ios::sync_with_stdio(false); .. 백준 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.. 백준 2473번 [세 용액](C++) -yes6686- 티스토리 백준 문제 풀이: 2473 [세 용액]문제 링크: https://www.acmicpc.net/problem/2473문제 설명:n개의 용액이 주어졌을 때, 세 용액을 혼합하여 그 특성값(합)의 절댓값이 0에 가장 가까운 조합을 찾는 문제입니다. 각 용액은 음수, 0, 양수로 이루어져 있으며, n은 최대 100,000입니다.문제 해결 코드#include #include #include using namespace std;long long int arr[100001];long long int resultArr[3];int main() { int n; cin >> n; for (int i = 0; i > arr[i]; } sort(arr, arr + n); long long in.. 백준 2467번 [용액](C++) -yes6686- 티스토리 백준 문제 풀이: 2467 [용액]문제 링크: https://www.acmicpc.net/problem/2467문제 설명:n개의 용액이 주어졌을 때, 두 용액을 혼합하여 그 특성값(합)의 절댓값이 0에 가장 가까운 두 용액을 찾는 문제입니다. 용액은 음수, 0, 양수로 구성되며, 두 용액을 혼합했을 때의 특성값은 두 용액의 합으로 정의됩니다.용액의 수 n은 최대 100,000개입니다.두 용액의 특성값이 0에 가까운 조합을 출력합니다.문제 해결 코드#include #include #include using namespace std;int arr[100001];bool compare(int a, int b) { return abs(a) > n; for (int i = 0; i > arr[i]; .. 백준 4030번 [포켓볼](C++) -yes6686- 티스토리 백준 문제 풀이: 4030 [포켓볼]문제 링크: https://www.acmicpc.net/problem/4030문제 설명:1부터 특정 자연수까지의 제곱수 중, 하나 적은 값이 삼각수인 수를 찾아 해당 범위 내 개수를 출력하는 문제입니다.삼각수는 아래와 같이 정의됩니다:T(n) = n * (n + 1) / 2주어진 두 수 (a, b)에 대해 a 문제 해결 코드#include #include #include #define INF 1000000000using namespace std;int cnt4[100001];map mp3;int main() { ios::sync_with_stdio(false); cin.tie(NULL); int s = 1; // 삼각수를 미리 계산하여 ma.. 백준 1166번 [선물](C++) -yes6686- 티스토리 백준 문제 풀이: 1166 (선물)문제 링크: https://www.acmicpc.net/problem/1166문제 설명:n개의 정육면체 선물을 상자(l × w × h)에 담으려고 합니다. 선물은 모두 같은 크기로 만들어야 하며, 가능한 가장 큰 선물의 한 변의 길이를 구하는 문제입니다. 길이는 소수점 아래 10자리까지 정확해야 합니다.문제 해결 코드#include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); // 입력 받기 double n, l, w, h; cin >> n >> l >> w >> h; // 이분 탐색 초기화 double s = 0; // 가능.. 이전 1 2 3 다음
