Jinho Tech

이분 탐색 Or 우선순위 큐 문제라는데, 이분 탐색이 훨씬 효율적일 것 같아서 그냥 이분 탐색으로 풀었다.

N, M = map(int, input().split())
li = list(map(int, input().split()))
s, e = 0, max(li)*M
res = 0
while s <= e:
    m = (s+e)//2
    if sum([m//n for n in li]) >= M:
        res = m
        e = m-1
    else:
        s = m+1
print(res)

기본적인 이분 탐색 문제이다.

while 1:
    n = int(input())
    if n == 0:
        break
    s, e = 1, 50
    while s <= e:
        m = (s+e)//2
        print(m, end=' ')
        if m == n:
            break
        elif m < n:
            s = m+1
        else:
            e = m-1
    print()

기본적인 이분 탐색 문제이다.

def bs(li, m):
    if li[1]-li[0] > m:
        return 0
    if li[-1]-li[-2] > m:
        return 0
    for i in range(1, len(li)-2):
        if (li[i+1]-li[i])/2 > m:
            return 0
    return 1

N, M = int(input()), int(input())
li = [0] + list(map(int, input().split())) + [N]
s, e = 0, N
res = 0
while s <= e:
    m = (s+e)//2
    if bs(li, m):
        e = m-1
        res = m
    else:
        s = m+1
print(res)

이분 탐색 문제이다. 처음에 e를 max(li)-2*K로 설정하는 허튼짓을 하는 바람에 엄청나게 많이 틀렸다. 

s가 0이면 0으로 나눌 경우가 생길 수 있기 때문에 1로 시작해야 된다. PyPy3로 제출해야 통과된다.

import sys

def count(li, m):
    t = 0
    for n in li:
        if n <= K:
            continue
        elif n < 2*K:
            n -= K
        else:
            n -= 2*K
        t += n//m
    return t
    
N, K, M = map(int, sys.stdin.readline().split())
li = [int(sys.stdin.readline()) for _ in range(N)]
s, e = 1, max(li)
res = 0
while s <= e:
    m = (s+e)//2
    if count(li, m) >= M:
        res = m
        s = m+1
    else:
        e = m-1
print(res if res else -1)

의외로 이분 탐색으로 풀 수 있는 문제이다. 내일 다시 한 번 풀어봐야겠다.

N, K = int(input()), int(input())
s, e = 1, K
ans = 0
while s <= e:
    m = (s+e)//2
    t = 0
    for i in range(1, N+1):
        t += min(N, m//i)
    if t >= K:
        ans = m
        e = m - 1
    else:
        s = m + 1
print(ans)

이분 탐색 or 수학 문제이다. 일단 그냥 수학으로 풀었는데 이분 탐색으로 어떻게 풀어야 될지 모르겠다.

수학 풀이

case = 1
while 1:
    a, b = map(int, input().split())
    if a == b == 0:
        break
    cnt = i = 0
    while (i+1)*i // 2 < a:
        i += 1
    while (i+1)*i // 2 < b-1:
        t = (i+1)*i // 2 + 1
        if t**0.5 == int(t**0.5):
            cnt += 1
        i += 1
    print(f"Case {case}: {cnt}")
    case += 1

이분 탐색 문제이다. 2차원 리스트의 총합과 최댓값을 알아야 문제를 풀 수 있어서 코드가 좀 길어진 것 같다.

def count(li, m, N):
    t = 0
    for i in range(N):
        for j in range(N):
            t += (m if m <= li[i][j] else li[i][j])
    return t

N = int(input())
li = []
max_li = sum_li = 0
for _ in range(N):
    a = list(map(int, input().split()))
    li.append(a)
    max_li = max(max_li, max(a))
    sum_li += sum(a)
s, e = 0, max_li
res = 0
while s <= e:
    m = (s+e)//2
    if count(li, m, N) >= sum_li/2:
        res = m
        e = m-1
    else:
        s = m+1
print(res)

이분 탐색 문제이다.

def count(li, m):
    t = 0
    for n in li:
        if n >= m:
            break
        t += m-n
    return t

N, K = map(int, input().split())
li = sorted([int(input()) for _ in range(N)])
s, e = min(li), max(li)+K
res = 0
while s <= e:
    m = (s+e)//2
    if count(li, m) <= K:
        res = m
        s = m+1
    else:
        e = m-1
print(res)

이분 탐색 문제이다. 

M, N = map(int, input().split())
li = list(map(int, input().split()))
s, e = 1, max(li)
res = 0
while s <= e:
    m = (s+e)//2
    if sum([n//m for n in li]) >= M:
        res = m
        s = m+1
    else:
        e = m-1
print(res)

이분 탐색 문제이다. 소수를 찾는 문제라서 반복문을 100번 정도 돌려줬다.

50번 정도 돌리면 결과의 오차가 10**-9보다 크게 나오는지 통과가 안된다.

N, L, W, H = map(int, input().split())
s, e = 0, max(L, W, H)
for _ in range(100):
    m = (s+e)/2
    if (L//m)*(W//m)*(H//m) >= N:
        s = m
    else:
        e = m
print("%.10f" %(e))

처음에 아래같이 풀었다가 시간 초과가 떠서 계속 틀렸다.

N, L, W, H = map(int, input().split())
s, e = 0, max(L, W, H)
while e-s > 0.00000001:
    m = (s+e)/2
    if (L//m)*(W//m)*(H//m) >= N:
        s = m
    else:
        e = m
print("%.10f" %(e))

이분 탐색 문제이다.

N, K = map(int, input().split())
li = [int(input()) for _ in range(N)]
s, e = 1, max(li)
res = 0
while s <= e:
    m = (s+e)//2
    t = sum(n//m for n in li)
    if t >= K:
        res = m
        s = m+1
    else:
        e = m-1
print(res)

이분 탐색 문제이다.

def count(li, m):
    t = cnt = 0
    for n in li:
        if t+n > m:
            t = n
            cnt += 1
        else:
            t += n
    return cnt+1

N, M = map(int, input().split())
li = [int(input()) for _ in range(N)]
s, e = max(li), sum(li)
res = 0
while s <= e:
    m = (s+e)//2
    if count(li, m) <= M:
        res = m
        e = m-1
    else:
        s = m+1
print(res)

이분 탐색 문제이다.

N, M = map(int, input().split())
li = [int(input()) for _ in range(N)]
s, e = 0, max(li)*M
res = 0
while s <= e:
    m = (s+e)//2
    t = sum([m//n for n in li])
    if t >= M:
        res = m
        e = m-1
    else:
        s = m+1
print(res)

이분 탐색 문제이다. 

def bs(li, n):
    s, e = 0, len(li)-1
    while s <= e:
        m = (s+e)//2
        if li[m] == n:
            return 1
        elif li[m] < n:
            s = m+1
        else:
            e = m-1
    return 0
        
for _ in range(int(input())):
    N = int(input())
    li1 = sorted(list(map(int, input().split())))
    M = int(input())
    li2 = list(map(int, input().split()))
    for n in li2:
        print(bs(li1, n))

그냥도 풀어봤다. 아이러니하게도 아래 코드가 속도가 더 빠르다.

for _ in range(int(input())):
    N = int(input())
    li1 = set(map(int, input().split()))
    M = int(input())
    li2 = list(map(int, input().split()))
    for n in li2:
        print(1 if n in li1 else 0)

이분 탐색 문제이다. 이제 이분 탐색에 조금 익숙해진 것 같다!

N = int(input())
li = sorted(map(int, input().split()))
res = 0
for i in range(N-1):
    s, e = i+1, N-1
    t = -1
    while s <= e:
        m = (s+e)//2
        if li[i] >= 0.9*li[m]:
            t = m
            s = m+1
        else:
            e = m-1
    res += t-i if t > -1 else 0
print(res)