이분탐색2 BOJ 2110 - 공유기 설치(C++) https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 두 공유기 사이의 거리에 대해 이분탐색을 이용 초기 값 -> left = 1, right = 공유기의 최대 좌표 1. mid = (left + right)/2 mid)로 했었는데 테스트 결과가 실패했음 문제에서의 거리는 공유기가 설치된 좌표까지 포함하는 거 였음 if(arr[i] - before >= mid) ex) 1, 3, 4 이고 거리.. 2021. 10. 14. BOJ 1756 - 피자굽기(C++) https://www.acmicpc.net/problem/1756 1756번: 피자 굽기 첫째 줄에 오븐의 깊이 D와 피자 반죽의 개수 N이 공백을 사이에 두고 주어진다. (1 ≤ D, N ≤ 300,000) 둘째 줄에는 오븐의 최상단부터 시작하여 깊이에 따른 오븐의 지름이 차례대로 주어진다. 셋 www.acmicpc.net 피자마다 오븐의 모든 지름을 탐색하는 완전 탐색의 경우 O(N*M)으로 300000의 데이터들을 탐색하면 시간 초과가 발생 이를 해결하기 위해 그리디 알고리즘을 적용하였으며, 풀이 후 검색해보니 이분탐색으로도 해결할 수 있다하여 이분탐색으로도 풀이 해봄 풀이 오븐의 너비는 이전 위치보다 현재 위치의 너비가 크다고해도 이전위치의 너비보다 큰 피자가 들어올 수 없다 더보기 ex) {3,.. 2021. 8. 26. 이전 1 다음
