백준(BOJ) 1654번 랜선자르기, 2805번 나무자르기(다시해야함)

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

 

처음에는 최소값을 주워진 k개의 랜선중 가장 짧은 랜선을 최솟값으로 해야 겠다고 생각함 ==>> 가장 짧은 랜선을 반드시 포함시키지 않아도 됨. n개만 만들수 있으면 되므로. ==>> 초기값을 가장짧은 1과 가장 길이가 긴 랜선의 중간값으로 두어보자!

 

 

from sys import stdin

def solution(arr, n):
    mini=1
    maxi=max(arr)
    while(mini<=maxi):
        evr=(mini+maxi)//2
        count=0
        for i in arr:
            count+=i//evr
        if(count>=n):
            mini=evr+1
        else:
            maxi=evr-1
    return maxi

def main():
    k, n=map(int,stdin.readline().split())
    arr=list()
    for _ in range(k):
        arr.append(int(stdin.readline()))
    print(solution(arr, n))

main()

 

2805. 나무자르기

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

 

이전에 풀었던 랜선자르기와 유사한 이진탐색문제로 코드안 for문안의 조건만 좀 수정해 주었다.

 

from sys import stdin

def solution(arr, m):
    mini=1
    maxi=max(arr)
    while(mini <= maxi):
        evr=(mini+maxi)//2
        total=0
        for i in arr:
            value=i-evr
            if(value>0):
                total+=value
        if(total>=m):
            mini=evr+1
        else:
            maxi=evr-1
    return maxi

def main():
    n, m = map(int,stdin.readline().split())
    arr=list(map(int, stdin.readline().split()))


    print(solution(arr, m))

main()