:: ADVANCE ::

BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2012 2512 예산 https://www.acmicpc.net/problem/2512 정답 찾아가는 이진 탐색 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include int n;int cost[10000];int limit;int sum[10001];int max; void solve(){ int s = 0, e = max, m; int cal, num; int i; while (s limit) e = m - 1; else s = m + 1; } printf("%d\n", e);} int main(){ int i; sca..

BAEKJOON ONLINE JUDGE 1920 수 찾기 https://www.acmicpc.net/problem/1920 이진 탐색 아.. 왜 나는 이진탐색 구현을 매번 실수하지.. quicksort 구현하면 0부터 마지막 배열까지 stl::sort : 0부터 마지막 + 1까지 (개수)binary search도 마찬가지로 left : 0, right : n - 1 까지 해야하는데 자꾸 n까지로 해서 값이 하나 잘못 들어가는 실수... 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#include int a[100010];in..

BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2004 2613 숫자구슬 https://www.acmicpc.net/problem/2613 최대값의 최소값이라는 말을 보고 이진탐색이라고는 생각하였지만 처음에는 DP로 접근해 보았다.DP로도 풀이가 생각났기 때문에.. dp[start][group] : start 지점부터 끝까지 group의 개수만큼 나누었을 때 그 합 중 최대값의 최소값을 저장그룹 하나, sum값과 그 외의 구간을 group - 1개로 나누었을 때 나오는 최소값 중 최대값들 중에서 최소값을 저장해 나갔다.그리고 저장해 나가면서 그 최소값이 되는 구간의 구슬 개수 또한 저장해 나갔다. sum 값은 입력을 받으면서 이중 반복문으로 sum[start][end]에 미리 ..

BAEKJOON ONLINE JUDGE 2110 공유기 설치 https://www.acmicpc.net/problem/2110 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include using namespace std; int home[200000]; int main(){ int n, c; int start = 1, end, cnt, middle, ans; int h; int i; scanf("%d %d", &n, &c); for (i = 0; i

BAEKJOON ONLINE JUDGE 2805 나무 자르기 https://www.acmicpc.net/problem/2805 H 높이를 찾는 이진 탐색을 하면 된다. H 값을 기준으로 잘린 나무의 합이 필요한 값보다 크면 더 큰 H를 찾아야 하고, 잘린 나무의 길이 합이 M보다 작으면 H는 더 낮아야 한다. 여기서, 문제의 특성을 잘 살펴보면 H 값이 변하면 잘린 나무의 값은 무조건 변하게 된다.따라서, 잘린 나무의 길이의 합이 M과 같으면 그 H값이 바로 최대값이다.하지만 여기서 잘린 나무의 길이 합이 딱 M과 같지 않을 수도 있기 때문에그럴 경우에는 합이 M보다 큰 마지막 경우의 end 값을 출력해 주어야 한다. (end를 출력하는 이유는 조건을 만족하는 마지막 middle에서 + 1을 한 값이 s..

BAEKJOON ONLINE JUDGE 1654 랜선 자르기 https://www.acmicpc.net/problem/1654 N개로 만들 수 있는 최대 랜선의 길이를 찾는 이진 탐색 문제 하나의 값을 가지고 N개 이상 만들 수 있으면 그 길이를 max와 비교, max를 갱신 한 후 길이를 늘려서 다시 탐색N개 보다 적게 만들면 길이를 줄여서 다시 탐색 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include int k, n;int line[10000];int max; void bsearch(long long int start, long long int end){ long long int mid..

BAEKJOON ONLINE JUDGE 2343 기타 레슨 https://www.acmicpc.net/problem/2343 정답을 찾아가는 이진 탐색 문제이다. 레슨의 길이를 기준으로 블루레이를 만들었을 때 만들 수 있는 블루레이의 개수가 M과 같거나 큰 경우다시 레슨의 길이를 더 크게 하여 가능 여부를 찾는다.레슨의 길이가 너무 큰 경우 블루레이의 개수가 M보다 작은 값이 나온다. 그 경우 다시 레슨의 길이를 줄여 탐색한다. 이런 식으로 이진 탐색 가능 여부를 만들어 탐색을 하여M을 만들 수 있는 가장 작은 레슨의 길이를 찾는다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#incl..