2343. [Python]기타 레슨

1. 문제

 

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

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 이분 탐색

 

3. 파이썬 코드

 

N, M = map(int, input().split())

num_list = list(map(int, input().split()))
# 시작 점과 끝점 설정을 블루레이 길이로 설정
start = max(num_list)
end = sum(num_list)
# 이분 탐색
while start <= end:
    middle = (start + end) // 2
    # 블루레이 한개씩 더해가며 값 체크
    value = 0
    # 블루레이 개수 체크
    cnt = 1
    for num in num_list:
        # 이전값 + 블루레이 반복문 값이 middle 값보다 작거나 같으면 더하고
        if value + num <= middle:
            value += num
        # 크면 값 갱신 후 블루레이 한개 추가
        else:
            value = num
            cnt += 1
    # 블루레이 개수가 M 보다 작거나 같으면 끝값을 중앙값 -1 로
    if cnt <= M:
        end = middle - 1
    # 외의 경우 시작값 갱신
    else:
        start = middle + 1
# 시작값 출력
print(start)

 

4. 문제를 풀고난 후 생각

 

• 평범한 이분 탐색과 같이 0 혹은 1로 초기값을 잡을 경우 불필요 연산 및 예외 케이스가 나올 수 있기 때문에 초기 시작값을 리스트 내에서 max 값으로 선언해준다.
• end 값으로는 결국 리스트를 모두 합한 값보다 클 수 가 없기 때문에 리스트를 합친 값으로 선언해주고 이분 탐색을 진행한다.
• 이분 탐색을 진행하며 리스트 내부를 순회해가며 값을 더하고 블루레이 개수를 체크하며 M 보다 작거나 같으면 끝 점을 땡겨오고 M 보다 크면 시작값을 증가시키고 이분 탐색이 끝났을때 start 즉 Lower bound 값을 출력하면 원하는 결과가 나온다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 이분 탐색