대학원생이 쉽게 설명해보기

K, N = map(int, input().split())
lengths = [int(input()) for _ in range(K)]

# 랜선의 최솟값은 1, 최댓값은 주어진 랜선 길이의 max 값
min_length = 1; max_length = max(lengths)
result = 0

while(min_length <= max_length):
    mean_length = (min_length + max_length) // 2
    
    cut_num = 0
    for length in lengths:
        cut_num += length // mean_length
    
    # 잘라진 랜선 개수가 N보다 많으면,
    # mean_length 밑에 존재하는 길이는 볼 필요가 없음.
    if(cut_num >= N):
        result = mean_length
        min_length = mean_length + 1

    # 잘라진 랜선 개수가 부족하다면,
    # mean_length 위에 존재하는 길이로는 조건을 만족할 수 없음.
    elif(cut_num < N):
        max_length = mean_length - 1
    
print(result)

1. 시간 초과

def iter_check(check_num, index, start, end):
    left_cnt = 0; right_cnt = 0
    left_index = 1; right_index = 1

    # 왼쪽에 숫자가 몇개 있는지
    while(start <= index - left_index):
        if(sorted_card_nums[index - left_index] == check_num):
            left_cnt += 1; left_index += 1
        else:
            break
            
    # 오른쪽에 숫자가 몇개 있는지    
    while(index + right_index <= end):
        if(sorted_card_nums[index + right_index] == check_num):
            right_cnt += 1; right_index += 1
        else:
            break
        
    # +1은 자기 자신을 의미함
    return left_cnt + right_cnt + 1

def solve(check_num, start, end):
    if(start > end):
        return 0
    
    index = (start + end) // 2
    
    # 이분 탐색
    if(sorted_card_nums[index] == check_num):
        return iter_check(check_num, index, start, end)
    elif(sorted_card_nums[index] > check_num):
        return solve(check_num, start, index - 1)
    else:
        return solve(check_num, index + 1, end)

import sys
input = sys.stdin.readline
    
N = int(input())
card_nums = list(map(int, input().split()))
sorted_card_nums = sorted(card_nums)

M = int(input())
target_list = list(map(int, input().split()))

results = []
start = 0
end = len(sorted_card_nums) - 1
    
for target in target_list:
    results.append(solve(target, start, end))
    
print(*results)

2. 자주 쓰는 딕셔너리 방법
(검색해보니 이 방법이랑 Counter 모듈이 쓰이고 있음)

import sys
input = sys.stdin.readline
    
N = int(input())
card_nums = list(map(int, input().split()))

M = int(input())
target_list = list(map(int, input().split()))

dicts = {}

for check_num in card_nums:
    if(check_num in dicts):
        dicts[check_num] += 1
    else:
        dicts[check_num] = 1
        
# ' '을 사이에 두고 반복하는 문자를 붙임
print(' '.join(str(dicts[target]) if target in dicts else '0' for target in target_list))

# ---------------------------------------
# result = ''

# for target in target_list:
#     if(target in dicts):
#         result += str(dicts[target])
#         result += ' '
#     else:
#         result += '0 '

# print(result[:-1])

def half_check(check_num, check_list):
    list_len = len(check_list)
    
    if(list_len == 0):
        return print('0')
    
    index = list_len // 2
    
    if(check_list[index] == check_num):
        return print('1')
    elif(check_list[index] > check_num):
        return half_check(check_num, check_list[:index])
    else:
        return half_check(check_num, check_list[index + 1:])

import sys
input = sys.stdin.readline    

N = int(input())
A = list(map(int, input().split()))
sorted_A = sorted(A)

M = int(input())
M_list = list(map(int, input().split()))

for check_num in M_list:
    half_check(check_num, sorted_A)

설명에 어렵다고 하길래 해봤더니, 직접 짠 코드는 시간초과...

이번 문제는 다량 참조하였다. 이 문제를 푼다면 '꼭' closest point 문제에 대한 이론적 개념을 이해하고 넘어가길 바란다. 보다보면 재밌다.

시간초과 코드 참고: https://hon6036.github.io/%EB%B6%84%ED%95%A0%20%EC%A0%95%EB%B3%B5/2261/
이론 참고: https://casterian.net/archives/92
(이론 블로그는 위 블로그에서 연결되어 있습니다.)

def dist(x1, x2):
    return (x1[0] - x2[0])**2 + (x1[1] - x2[1])**2

# 이론 블로그 참고
def solve(coords, N):
    # 점이 두 개일때는 두점 거리만 구하면 됩니다.
    if(N == 2):
        return dist(coords[0], coords[1])
    # 점이 세 개일때는 각 두점 사이의 거리를 구해서 최솟값을 구하면 됩니다.
    elif(N == 3):
        return min(dist(coords[0], coords[1]), dist(coords[1], coords[2]), dist(coords[0], coords[2]))
    
    mid = (coords[N//2][0] + coords[N//2-1][0]) // 2
    # x축을 기준으로 짧은 거리 d를 구합니다.
    d = min(solve(coords[:N//2], N//2), solve(coords[N//2:], N//2))
    
    # x 축 기준을 잊지 말것
    # 유효 거리 d보다 짧거나 같은 것을 제외하고 나머지는 제외시킵니다.
    # 즉, 두점 거리가 d보다 먼 경우는 제외합니다.
    short_check = []
    for subset in coords:
        if((mid - subset[0])**2 <= d):
            short_check.append(subset)
    short_check.sort(key = lambda x:x[1])
    
    if(len(short_check) == 1):
        return d
    else:
        y_check = d
        
        # x축만 고려하면 아직 고려해야할 점의 개수가 많이 남아있어 시간초과가 뜨게 됩니다.
        # 따라서 y축을 고려해주어 y축 기준의 d보다 긴 경우는 전부 제외시켜 주어야 합니다.
        # 세 가지 경우는 필수로 제외합니다.
        for i in range(len(short_check) - 1):
            for j in range(i+1, len(short_check)):\
                # y축 기준, 기본적으로 최소 길이 d보다 사이 거리가 긴 경우 제외
                if(short_check[i][1] - short_check[j][1]) ** 2 > d:
                    break
                # 두 점 모두 왼쪽에 있는 경우
                elif(short_check[i][0] < mid and short_check[j][0] < mid):
                    continue
                # 두 점 모두 오른쪽에 있는 경우
                # 두 점이 mid를 지나는 점과 비교해보세요
                elif(short_check[i][0] > mid and short_check[j][0] > mid):
                    continue
                y_check = min(y_check, dist(short_check[i], short_check[j]))
                
    return y_check

import sys

# input = sys.stdin.readline
N = int(input())
coords = [list(map(int, input().split())) for _ in range(N)]

# 중복되는 점은 제거
# 블로그 참고
coords_set = list(set(map(tuple,coords)))
if len(coords_set) != len(coords):
    print("0")
else:
    coords_set.sort() # sorted(coords, key=lambda x:-x[0])
    print(solve(coords_set, N))

서로 바뀐 내용이 충돌되서 pull이 되지 않는 경우입니다.

해결 방법은 매우 간단합니다.

git add -A
git stash
git pull