https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 마찬가지로 이분 탐색 문제. 이러한 유형들은 뭘 많이 자른다. 한가지 주의할 점은 랜선의 길이가 0이 되는 일은 없기 때문에 lo를 0이 아닌 1로 시작해야 한다. 안그러면 런타임 에러(ZeroDivisionError)가 뜨는데 코테에서 이에 해당하는 testcase를 주지 않으면 아무 생각 없이 지나갈 수도 있을것 같다. 주어진 테케 잘 돌아간다고 넘기지 말고 문제 ..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 계속되는 이분 탐색 시리즈. 이와 비슷한 류의 문제는 같은 방식으로 작성하는 연습을 하고 있다. 나무를 잘라보자 N, M = map(int, input().split()) trees = list(map(int,input().split())) lo = 0 hi = max(trees) mid = (lo+ hi) //2 def is_possible(mid): tm..

https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이분 탐색 중 파라매트릭 서치를 구현해보는 문제이다. 어렵게 생각하지 말고 기본적인 이분탐색 구현에 초점을 맞추면 쉽게 해결할 수 있다. 라이브러리를 불러와서 이분탐색 함수를 쓸 필요도 없다. 입력받은 예산들 중 가장 큰 값의 절반으로 중간점을 잡고 중간점과 각 예산 중 작은 값들을 더한 값이 예산 총액을 넘어가는지 확인하면서 이를 반복한다. N = int(input()) req = list..