결정알고리즘

결정알고리즘

유효한 답의 범위가 있는 알고리즘
근데 그 답의 범위에서 최대 또는 최소를 찾는 문제
문제를 보았을 때 답의 범위가 보임
특정 값이 값으로서 유효한가, 유효하지않은가를 판별 할 수있는 알고리즘
최소, 최대 키워드

풀이 방법

• 이분검색 활용
• 답의 범위를 정한 후, 답으로서 유효한지를 판별
• start, end, mid로 답의 범위를 좁혀나가는 방식

예시 문제

n개의 선이 있을 때, 이 선들을 잘라 같은 길이의 선 k를 만들고자 한다.
n은 k보다 클 수 없을때, 최대 길이의 공통된 선의 길이는?
첫번째 줄에는 각각 n, k이며 두번째 줄 부터는 n개의 선의 길이이다.

4 11
802
743
457
539

코드

k, n = map(int, input().split())
lines = []

for _ in range(k):
    lines.append(int(input()))

# 최대 길이의 선을 찾는 함수
def find_ans(lst, s, e, res):
    if s > e:   # s가 e보다 클때는 이분검색이 끝난 것
        return res

    mid = (s+e) // 2
    total = 0   # 자른 선의 총 갯수

    for i in lst:
        total += i // mid

    if total < n:   # n보다 작을 때는 선의 길이가 더 짧아야하므로 end를 mid-1로 범위를 줄임
        return find_ans(lst, s, mid-1, res)
    else:  # n보다 크거나 같을 경우에는 선의 길이가 더 길어도 됌. start를 mid+1로 범위를 줄임
        res = mid   # 일단 res에 공통 선의 길이 값을 담아줌
        return find_ans(lst, mid+1, e, res)


print(find_ans(lines, 1, max(lines), 0))