[알고리즘/이분 탐색] 6236번 : 용돈 관리 - python

링크 : https://www.acmicpc.net/problem/6236

6236번: 용돈 관리

 

---

• 문제
• 소요시간: 1시간(19%) 실패

---

• 설계하기(접근방법) 

1. 입력받기

쓸 돈을 입력받는다

양이 많으니

sys를 통해 입력받자

2. 구현하기

start를 잘못 잡았다

 

start값은 항상 쓸돈의 최대치보다는 커야하는데

평균으로 구해버렸다

 

start = max(plan)

end = sum(plan) -> 동전 플랜의 총합

 

으로 잡고 이진탐색을 해준다

 

만약 현재 잔액이 쓸 돈보다 큰 경우

잔액에서 쓸 돈을 빼준다

 

만약 부족한 경우에는

현재 금액을 반납하고

mid 금액으로 초기화해준 후

잔액에서 쓸 돈을 빼준다

 

 

3. 출력하기

마지막 start 값을 출력한다

 

---

• 코드(출력)

import sys
input = sys.stdin.readline

day, trial = map(int,input().split())
plan = [int(input()) for _ in range(day)]


start = max(plan)
end = sum(plan)

while start <= end:
    mid = (start + end) // 2
    budget = mid
    cnt = 1
    for i in plan:
        if budget < i:
            # 반납 후 인출
            budget = mid
            # 인출 횟수
            cnt += 1
        # 차감
        budget -= i
    if cnt > trial :
        start = mid + 1
    else:
        end = mid - 1
print(start)

 

---

• 얻어갈 부분

1. 이진 탐색의 경우 start와 end값을 잘 잡아야 한다는 것을 배웠다.