• BOJ_1654_랜선자르기

import sys
input=sys.stdin.readline
k, n = map(int, input().split())
li=[0]*k
for i in range(k):
    li[i]=int(input())
standard = max(li)
res=0
def binary(low, high):
    if high<low:
        return
    global n
    global res
    mid=(low+high)//2
    temp=0
    for i in li:
        temp+=i//mid
    if temp>=n:
        res=mid   
        binary(mid+1, high)
    else:
        binary(low, mid-1)
binary(0, standard*2)
print(res)

Parametric Search를 사용하기 위해서는 문제를 결정 문제로 바꿀 수 있어야 한다.

위 문제의 경우 자를 랜선의 길이를 임의로 x라고 했을 때 랜선 N개를 만들 수 있다면 True를, 없다면 False를 반환하는 문제로 바뀌게 된다.

그리고 이 중간 값인 mid는 401이 될 것이고 mid 길이 만큼 자를 때 랜선 N개를 만들 수 있다면 mid보다 더 크게 잘라도 되는지를 확인해야 하기 때문에 low에 mid+1 값을 넣어서 반한다.

만약 만들 수 없다면 그 보다 더 짧게 잘라야 하므로 high에 mid-1 값을 넣어서 반복한다.

그러다 high가 low보다 작아지는 순간에 반복을 멈춘다.

시간 복잡도를 계산해보면 우선 랜선 N개를 만들 수 있는지 판단할 때의 시간 복잡도는 O(N)이다.

현재 가지고 있는 모든 랜선에 대해서 각각 mid로 나눈 값(소숫점 버림)을 모두 더해서 N과 비교하면 되기 때문이다.

그리고 가장 최대 길이를 찾기 위한 과정은 이분 탐색으로 진행되기 때문에 시간 복잡도는 O(log N)이다.

[출처] https://growth-coder.tistory.com/127

• BOJ_2776_암기왕

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
		n = int(input(())
		nums1 = set(map(int, input().split()))
		m = int(input(())
		nums2 = list(map(int, input().split()))
		for num in nums2:
				if num in nums1:
						print(1)
				else:
						print(0)