본문 바로가기

Algorithm/BOJ133

[백준] 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.
[백준] 1253번 - 좋다 (파이썬) # 좋다 import sys input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) arr.sort() result = 0 for i, num in enumerate(arr): temp = arr[:i]+arr[i+1:] left, right = 0, len(temp)-1 while left num: right -= 1 elif temp[left]+temp[right] < num: left += 1 else: result += 1 break print(result) 투포인터 1. 입력을 받고 정렬을 해준다. 2. arr의 각 수 num마다 num을 .. 2022. 3. 29.
[백준] 16434번 - 드래곤 앤 던전 (파이썬) # 드래곤 앤 던전 N, A = map(int, input().split()) arr = [] for _ in range(N): type, atk, hp = map(int, input().split()) arr.append((type, atk, hp)) def can_clear(curATK, maxHP): curHP = maxHP # 모든 방 탐색 for type, atk, hp in arr: # 몬스터 if type == 1: turn = hp//curATK if not hp % curATK else hp//curATK+1 # 용사가 먼저 공격하므로 -1 curHP -= atk * (turn-1) # 물약 else: curATK += atk curHP += hp # 최대 회복은 maxHP까지만 if c.. 2022. 3. 28.
[백준] 2022번 - 사다리 (파이썬) # 사다리 from math import sqrt x, y, c = map(float, input().split()) start, end = 0, min(x, y) def get_c(mid): a = sqrt(x**2-mid**2) b = sqrt(y**2-mid**2) return a*b/(a+b) result = 0 while end-start > 1e-6: mid = (start+end)/2 if get_c(mid) >= c: result = mid start = mid else: end = mid print("{}".format(round(result, 4))) 이분탐색 1. end를 둘 중 작은 값으로 설정 2. 이분탐색 - end-start가 1e-6(10^-6)보다 클 때까지 반복 (오차가 .. 2022. 3. 27.
[백준] 3649번 - 로봇 프로젝트 (파이썬) # 로봇 프로젝트 while True: try: x = int(input())*10000000 n = int(input()) arr = [int(input()) for _ in range(n)] arr.sort() answer = [] left, right = 0, n-1 while left x: right -= 1 else: answer = [arr[left], arr[right]] break if answer: print('yes {0} {1}'.format(answer[0], answer[1])) else: print('danger') except: break 투포.. 2022. 3. 26.
[백준] 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.

티스토리툴바