binary-search3 [BOJ] 1654번: 랜선 자르기 https://www.acmicpc.net/problem/1654 랜선 하나의 길이를 이분탐색하자. #include #include using namespace std; int k, n, lan[1000001], Max = -987654321; int main() { scanf("%d %d", &k, &n); for (int i = 0; i 1; int cnt = 0; for (int i = 0; i = n) .. 2018. 8. 9. [BOJ] 2805번: 나무 자르기 https://www.acmicpc.net/problem/2805 나무를 자르는 것을 이분 탐색으로 구할 수 있다. 1부터 주어진 나무의 최대 길이까지 이분 탐색을 하면서 잘라서 얻은 나무가 더 많으면 위 부분으로 조절하면 되고 반대로도 같은 방식으로 하면 된다. 하지만 그 필요한 양만큼만 못 가져갈 때도 있으므로 그럴땐 한 번 더 mid를 구한 것이 답이다. 참고: 파라매트릭 서치 #include #include using namespace std; int n, m, maxH = -987654321, tree[1000001]; int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) { scanf("%d", &tree[i]); maxH = ma.. 2018. 8. 9. [BOJ] 10815번: 숫자 카드 https://www.acmicpc.net/problem/10815 이분 탐색 #include #include using namespace std; int n, m, ar[500001]; bool bs(int find) { int s = 0, f = n - 1; while (s find) f = mid - 1; else s = mid + 1; } return 0; } int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &ar[i]); sort(ar, ar + n); scanf("%d", &m); while (m--) { int a; scanf("%d", &a); printf("%d ", bs(a)); } return 0; } 2018. 8. 9. 이전 1 다음
