2512. [Python]예산

1. 문제

 

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

2512번: 예산

 

2. 접근 방법

 

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

 

3. 파이썬 코드

 

import sys

N = int(input())
# 돈 리스트 받아오기
money_list = list(map(int,input().split()))
# 돈의 총합
total_money = sum(money_list)
# 제일 많은 돈
max_money = max(money_list)
# 제한된 돈
limit_money = int(input())
# 돈의 총합이 제한된 돈보다 작을 경우 max 값 출력
if total_money <= limit_money:
    print(max_money)
else:
    # 최대로 얼마를 넣을 수 있는지 변수로 최소값 저장
    max_answer = -sys.maxsize
    # 최고값일떄의 인덱스
    max_index = 0

    check_list = []
    # 0 ~ 제일 많은 돈까지 check_list에 저장
    for i in range(max_money+1):
        check_list.append(i)
    # check_list 길이 저장
    check_length = len(check_list)
    # 이분탐색을 위한 left, right 값
    left = 0
    right = check_length
    # left 값이 right 값보다 커지면 탈출
    while left <= right:
        # 각 돈에 대해서 얼마만큼 가격이 나오는지
        check_total = 0
        # 중앙값
        middle = (left+right)//2
        # money_list에서 값을 한개씩 순회하며
        for i in money_list:
            # i 값이 정해진 돈의 값보다 작거나 같은경우 check_total에 i 더함
            if i <= check_list[middle]:
                check_total += i
            # 큰 경우 제한된 돈의 값을 더해줌
            else:
                check_total += check_list[middle]
        # 기존에 최대로 제한된 돈과 기준값으로 제한시킨 돈의 총합을 비교하여 작으면 인덱스와 총합 값을 최신화
        if check_total < limit_money:
            left = middle + 1
            if max_answer < check_total:
                max_answer = check_total
                max_index = middle
        # 클 경우 right 값만 조정
        elif check_total > limit_money:
            right = middle - 1
        # 제한된 값과 같을경우 값을 갱신 후 break
        else:
            max_answer = check_total
            max_index = middle
            break
    print(max_index)

 

4. 문제를 풀고난 후 생각

 

• 이분 탐색으로 탐색을 최소한으로 진행하며 원하는 목표값을 찾아 가는 방식으로 해결했다.
• 문제를 읽어보며 돈의 값이 limit_money(제한된 돈의 값)보다 돈의 총합이 더 작은 경우 리스트에서 max_money 만 골라서 출력하는 것으로 필요없는 연산을 시행하지 않았다.
• 이후 총합이 더 큰 경우 0 ~ max_money 까지 리스트를 생성하여 이분 탐색을 진행하였다.
• 이분 탐색으로 값을 골라 각 저장된 money_list 에서 큰 경우 중앙값으로 선택된 값을 더해줬고, 작은 경우 그 값을 그대로 더해주는 방식으로 돈의 총합을 구해줬다.
• 구한 돈의 총합을 limit_money 와 값을 비교해 가며 작은 경우 그 돈의 총합을 변수에 저장한 후 인덱스 값도 같이 저장 해 주었다.
• 큰 경우는 이분 탐색의 우측값만 갱신해줬고 같은 경우는 더이상 탐색할 필요가 없어서 값을 갱신 후 break를 걸어줬다.

 

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

 

• 이분 탐색