반응형
이녀석을 처음 만난 것은 1654번이다.
나는 평범하게 이 녀석의 모든 경우를 계산해서 해결하려고 했다.
k,n=map(int,input().split())
a=[]
res=[]
for _ in range(k):
a.append(int(input()))
for y in range(1, min(a)+1):
cnt=0
for x in a:
cnt=cnt+x//y
if(cnt>=n):
res.append(y)
print(max(res))결과는 시간초과.
그래서 찾다가 알게된 이진탐색.
아래는 개념이다.
이진탐색(Binary Search)
데이터가 정렬되어 있는 배열에서 특정 값을 찾아내는 알고리즘이다.
배열 중간의 값을 골리 찾는 값과 비교하고, 중간 값이 찾는 값보다 작으면 최소값을 중간값 +1로 바꾼다.
반대로 중간값이 찾는 값보다 크면, 최대값을 중간값 -1로 바꾸어 반복한다.
이진탐색이라는 이름이 붙여진 이유는 처음 N 크기의 배열이 한 단계가 지나갈 때마다 1/2배 되기 때문이다.
따라서 시간복잠도는 O(logN)이 된다.
따라서 보통의 이진탐색은 이렇게 짠다
k,n=map(int,input().split())
a=[]
res=[]
for _ in range(k):
a.append(int(input()))
a.sort()
low=1
top=min(a)
while 1:
mid=(low+top)//2
cnt=0
for x in a:
cnt=cnt+x//mid
if cnt>n:
low=mid+1
elif cnt<n:
top=mid-1
else:
print(mid)
break하지만, 이건 만족하는 숫자를 탐색하면 바로 출력하는 알고리즘이다.
위 문제에서 원하는것은 랜선 길이의 최대값.
즉 가장 긴 랜선을 찾아야한다.
그래서 while의 조건을 통해 탐색이 가능할 때까지 계속 탐색해야한다.
그래서 코드는 다음과 같다.
k,n=map(int,input().split())
a=[]
res=[]
for _ in range(k):
a.append(int(input()))
a.sort()
low=1
top=min(a)
while low<=top:
mid=(low+top)//2
cnt=0
for x in a:
cnt=cnt+x//mid
if cnt>=n:
low=mid+1
else :
top=mid-1
print(top)top을 출력해주는 이유는 if cnt>=n:에 의해 low값은 마지막보다 1이 커지기 때문이다.
거의 동일한 유형으로 2805번이 있다.
동일하게 풀면된다. 중간 계산만 달라질 뿐이다.
n,m=map(int, input().split())
namu=list(map(int, input().split()))
low=1
top=max(namu)
while low<=top:
d=0
mid=(top+low)//2
for x in namu:
if (x-mid)>=0:
d=d+(x-mid)
if d>=m:
break
if d<m:
top=mid-1
elif d>=m:
low=mid+1
print(top)반응형
