EDOC 2023-2 6주차 과제

05-3. 이진 탐색

 

029. 수 찾기 (백준 1920번)

 

https://www.acmicpc.net/problem/1920

 

from sys import stdin

n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
m = int(stdin.readline())
data = list(map(int, stdin.readline().split()))

a.sort()

for x in data:
    find = False
    start = 0
    end = len(a) - 1
    while start <= end:
        mid = (start + end) // 2
        if a[mid] > x:
            end = mid - 1
        elif a[mid] < x:
            start = mid + 1
        else:
            find = True
            break
    if(find):
        print(1)
    else:
        print(0)

 

(정답)

 

---

 

030. 기타 레슨 (백준 2343번)

 

https://www.acmicpc.net/problem/2343

 

from sys import stdin

n, m = map(int, stdin.readline().split())
lsn = list(map(int, stdin.readline().split()))

start = 0
end = 0

for i in lsn:
    if i > start:
        start = i
    end += i

while start <= end:
    mid = (start + end) // 2
    sum = 0
    cnt = 1
    for i in range(n):
        sum += lsn[i]
        if sum > mid:
            sum = lsn[i]
            cnt += 1
    if cnt > m:
        start = mid + 1
    else:
        end = mid - 1

print(start)

 

(정답)

 

---

 

031. K번째 수 (백준 1300번)

 

https://www.acmicpc.net/problem/1300

 

from sys import stdin

n = int(stdin.readline())
k = int(stdin.readline())

start = 1
end = n*n
ans = 0

while start <= end:
    mid = (start + end) // 2
    cnt = 0
    for i in range(1, n+1):
        cnt += min(mid//i, n)
    if cnt < k:
        start = mid + 1
    else:
        ans = mid
        end = mid - 1

print(ans)

 

(정답)