시나위

https://www.acmicpc.net/problem/18113 18113번: 그르다 김가놈 첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다. www.acmicpc.net 이분탐색 문제이다. 손질된 김밥(꼬다리를 제거한 김밥)을 사용해서 김밥 조각 M개 이상을 만들면 되고, 이분탐색으로 김밥 조각을 내는 길이를 찾으면 된다. # import sys; input = sys.stdin.readline def remove_kkodari(dist, K): if dist = K: dist -= K return dist def bin..

https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 확률 Z값을 구하고, s와 e의 중간값으로 만든 새로운 확률이 Z보다 큰 값을 찾으면 된다. 그리고 커지는 값중에 최솟값을 찾아야하니 s가 e보다 커지는 값을 종료 조건으로 반복문을 설정해서 이분탐색을 하면 된다. def main(): X, Y = map(int, input().split()) Z = (Y * 100) // X s, e = 0, X while s

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분탐색 문제이다. 높이를 오름차순으로 정렬하고 시작점은 0, 끝점은 가장 큰 값(정렬했으므로 마지막 값)으로 설정해서 이분탐색을 한다. 합이 M보다 작거나 같을때는 최솟값을 올리고, 작을때는 최댓값을 내려서 탐색한다. 이때 합도 이분탐색으로 찾는데 처음에 누적합을 구하고, 처음으로 목표값 보다 커지는 인덱스를 찾으면 해당 구간에서의 합을 쉽게 구할수 있다...

www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net import sys input = sys.stdin.readline N = int(input()) N_list = list(map(int, input().split())) N_list.sort() M = int(input()) M_list = list(map(int, input().split())) # M_list의 원소가 N_list에 존재하는지 알아내는 문제 ..

www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net K, N = map(int, input().split()) N_list = [int(input()) for _ in range(K)] result = 0 s, e = 1, max(N_list) while s m의 값이 큰경우 => m을 줄이는 방향 e = m - 1 else: s = m + 1 result = max(result, m) # 랜선의 최대 길이를 찾아야 하므로 print..

www.acmicpc.net/problem/13706 13706번: 제곱근 첫째 줄에 양의 정수 N이 주어진다. 정수 N의 제곱근은 항상 정수이며, N의 길이는 800자리를 넘지 않는다. www.acmicpc.net # 내가 푼 방식 from math import isqrt print(isqrt(int(input()))) sqrt로도 해봤는데 에러가 났다. 자리수가 커서 소수점이 생기면 오버플로우 에러가 뜬다고 한다. 그래서 integer인경우에 사용 가능한 isqrt가 있다고 해서 사용했고 통과했다. 사실 이렇게 푸는 문제는 아닌것 알고 있었다. 이분탐색을 제대로 사용하지 못해 이렇게 시도했다 # 이분탐색 n = int(input()) low = 1 high = n while 1: mid = (low ..