[코드트리 기준을 새로 설정하여 완전탐색] 구간 잘 나누기 Python

처음으로 답지보고 풀었다.

최소의 최대, 최소의 최대 이런 문제 풀 때는

반드시 그 범위를 설정하고 하나씩 가능한 값인지 생각하는 아이디어를 기억해야겠다.

# n, m 입력
n, m = map(int, input().split())
# num_list
num_list = list(map(int, input().split()))

# 함수들
# is_possible(curr_possible_max)
def is_possible(curr_possible_max):
    
    # curr_sum
    curr_sum = 0
    # curr_section
    curr_section = 1

    for i in range(n):
        
        # 하나라도 숫자가 curr_possible_max보다 크면
        if num_list[i] > curr_possible_max:
            # 실패
            return False
        
        # 이번 숫자가 들어갔을때 curr_possible_max보다 크면
        if curr_sum + num_list[i] > curr_possible_max:
            # curr_sum 초기화
            curr_sum = 0
            # 섹션 수 추가
            curr_section += 1
        
        # 이번 숫자 넣어주기
        curr_sum += num_list[i]
    
    # 최종적으로 나눈 섹션 수가 m보다 작거나 같으면
    if curr_section <= m:
        # 성공
        return True

# 설계
# min_range, max_range (최댓값이 될 수 있는 최솟값과 최댓값)
min_range, max_range = 1, sum(num_list)

# 최댓값이 될 수 있는 범위 내에서 탐색
for possible_max in range(min_range, max_range + 1):
    # 최댓값이 될 수 있으면
    if is_possible(possible_max):
        # 출력
        print(possible_max)
        # 반복문 종료
        break