백준 1654 랜선 자르기

이상현·2021년 7월 5일
0

알고리즘_문제풀이

목록 보기
32/45
post-thumbnail

랜선 자르기

문제는 백준에서 확인 할 수 있다.


✔ 접근방법

  • 이분 탐색 문제

만족하는 조건을 찾아 대상을 절반씩 나누어가며 탐색


✔ 코드


import sys

def solution(arr, max_val):
    global N
    answer = 0
    left = 0
    right = max_val
    ## zero_division 에러 방지
    if right == 0:
        print(0)
        exit()

    mid = (left + right)//2 if (left + right)//2 != 0 else 1
    while(left <= right):
        cnt = 0
        
        for elem in arr:
            cnt += elem // mid
        
        ## 나누어진 숫자가 부족하다면, 더 작은 단위로 쪼개야 함
        if cnt < N:
            right = mid-1
        else:
            left = mid+1

        ## 조건을 만족하는 길이 중 최대 길이
        if cnt >= N and answer < mid:
            answer = mid


        # print(left, right, mid)
        if mid == 1:
            break
        mid = (left + right) // 2 if (left+right)//2 else 1

    print(answer)


if __name__ == "__main__":
    K, N = map(int, input().split())
    arr = []
    max_val = 0
    for _ in range(K):
        val = int(sys.stdin.readline().rstrip())
        arr.append(val)
        if val > max_val:
            max_val = val
    
    solution(arr, max_val)


☝ 팁

  • 값의 범위를 확인하였을 때, 너무 크다 싶으면 이분탐색을 고려한다.
  • 테스트케이스

2 7 (1~ 잘못된 값 나올때까지 해봄)
10
0
값 : 1

2 2
2
0
값 : 1

profile
'당신을 한 줄로 소개해보세요'를 이 블로그로 대신 해볼까합니다.

0개의 댓글