본문 바로가기

이분탐색13

[백준] 1477번 - 휴게소 세우기 (파이썬) # 휴게소 세우기 N, M, L = map(int, input().split()) arr = [0]+list(map(int, input().split()))+[L] arr.sort() start, end = 1, L-1 result = 0 while start mid: # 나눈 만큼 휴게소를 설치 (현재 설치 돼있는 구역은 제외해야해서 -1) count += (arr[i]-arr[i-1]-1)//mid if count > M: start = mid+1 else: end = mid-1 result = mid print(result) 이분탐색 1. 입력을 받으면서 휴게소 배열(arr)의 양 끝에 출발지점과 도착지점을 추가해주고 정렬 2. start, end는 휴게소 위치의 범위 3. 이분탐색 - mid : .. 2022. 3. 30.
[백준] 3079번 - 입국심사 (파이썬) # 입국심사 import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = [] for _ in range(N): arr.append(int(input())) annswer = 0 left, right = 0, max(arr)*M while left M: break if people < M: left = mid + 1 else: right = mid - 1 answer = mid print(answer) 이분탐색 1. right을 가장 심사가 오래 걸리는 곳에서 모두 검사할 때의 시간으로 초기화 2. 이분탐색 - 해당 시간으로 입국심사를 할 수 있는 사람의 수 구하기 - 사람의 수가 M보다 작으면 left = mid +1 - 아니.. 2022. 3. 25.
[백준] 2343번 - 기타 레슨 (파이썬) # 기타 레슨 N, M = map(int, input().split()) arr = list(map(int, input().split())) answer = 0 left, right = max(arr), sum(arr) while left mid: count += 1 sum = 0 sum += arr[i] if sum: count += 1 if count > M: left = mid + 1 else: right = mid - 1 answer = mid print(answer) 이분탐색 1. left는 동영상 길이의 최솟값, right은 동영상 길이의 최댓값 2. 이분탐색 - 강의를 순서대로 블루레이에 넣는다. 길이는 mid - 강의를 넣고 나온 블루레이의 개수가 M보다 크다면 left = mid +1 -.. 2022. 3. 25.
[백준] 8983번 - 사냥꾼 (파이썬) # 사냥꾼 import sys input = sys.stdin.readline M, N, L = map(int, input().split()) shots_place = list(map(int, input().split())) animals_place = [] for i in range(N): a, b = map(int, input().split()) animals_place.append((a, b)) answer = 0 shots_place.sort() for a, b in animals_place: start, end = 0, len(shots_place)-1 mid = 0 while start < end: mid = (start+end)//2 if shots_place[mid] < a: start =.. 2022. 3. 23.
[프로그래머스] 고득점Kit (9) - 이분탐색 (파이썬) 1. 입국심사 (Lv. 3) # 입국심사 def solution(n, times): answer = 0 times.sort() left, right = 1, max(times)*n while left = n: answer = mid right = mid - 1 elif temp < n: left = mid + 1 return answer right = max(times)*n : 가장 긴시간으로 n명이 입국심사를 했을 때가 최댓값 이분탐색 실시 - mid : 걸린 총 시간 - temp : 해당 시간 안에 입국 심사를 할 수 있는 사람의 수 - temp == n 을 목표로 이분탐색을 진행 2. 징검다리 (Lv. 4) # 징검다리 def solution(distance, rocks, n): answer = 0.. 2022. 3. 12.
[백준] 1939번 - 중량제한 (파이썬) # 중량제한 import sys from collections import deque MAX = sys.maxsize input = sys.stdin.readline N, M = map(int, input().split()) arr = [[] for _ in range(N+1)] weight = [MAX] * (N+1) for _ in range(M): a, b, cost = map(int, input().split()) arr[a].append((b, cost)) arr[b].append((a, cost)) start_city, arrive_city = map(int, input().split()) def bfs(mid): q = deque() q.append(start_city) visited[sta.. 2022. 2. 4.

티스토리툴바