문제 이름 : 2512번_예산
풀이 :
-
Key point (생략가능)
- 모든 가능한 경우의 수를 다 생각해주자 (10/1,1,1,1,11,11,11,11,11,100/100 의 경우 41이 나와야함)
- 이진 탐색 을 떠올릴 수 있었다면,,,당신은 성공
-
Logic :
지역별로 요청한 금액의 총 합을 임시 예산금이라고 하자.
임시 예산금이 예산보다 작거나 같다면 요구한대로 전부 지원해주면 된다.
문제는 임시 예산금이 큰 경우이다.
임시 예산금이 큰 경우 상한액을 정해 상한액보다 요청 금액이 큰 지역에게는 전부 상한액을 지급하도록 하자는 것이 문제의 요구조건이다.
여기서 그러면 상한액을 어떤식으로 구할지가 관건이다.
처음에 나는 예산금의 평균에서 산수를 이리저리 해서 상한액을 구하는 알고리즘을 생각했는데 이럴 경우,
(10/1,1,1,1,11,11,11,11,11,100/100) 이라는 입력값이 들어올 경우 틀린다.
결론적으로 이진탐색을 통해 상한액을 구할 수 있다.
지역 별 요청 금액 중 가장 큰 값을 끝 값으로 정한다. 그리고 0 원을 시작 값으로 정한다.
시작값이 끝값보다 커지기 전까지 다음의 로직을 반복한다.
-
끝 값과 시작 같의 중간 값을 구한다. 중간 값이 문제에서 말하는 상한액이 된다.
-
임시 예산금을 다시 계산하는데, 이때 상한액보다 큰 경우 상한액으로 바꿔서 계산해준다.
-
계산된 임시 예산금이 예산보다 크다면 끝 값은 조정한다.( 끝 값 = 중간 값 +1)
-
임시 예산금이 작거나 같다면 시작 값을 조정한다. ( 시작 값 = 중간 값 +1)
# 34400kb / 68ms import sys import math input = sys.stdin.readline ''' 4 (지역) 120 110 140 150 (지역별 예산 요청) 485(한도)''' def main(): state_number= int(input()) # 지역 수 budget_request = list(map(int,input().split())) # 각 지역별 예산 요청 금액 budget = int(input()) # 예산 if sum(budget_request) <= budget: # 예산 요청 금액의 총 합이 예산 보다 작은 경우 print(max(budget_request)) return # 예산보다 예산 요청 금액의 총 합이 큰 경우 budget_request.sort() start = 0 end = max(budget_request) result = 0 while (start <= end): mid = (start + end )//2 # mid 가 상한액 temporary_budget =0 for i in range(state_number): # 임시 예산의 총 합 구하기 (요청 금액이 mid 보다 크면 mid로 요청 금액 계산하기) temporary_budget += min(mid,budget_request[i]) if budget >= temporary_budget: # 예산이 임시 예산 총 합이 예산보다 크거나 같으면 result = mid start = mid +1 else: end = mid -1 print(result) main()
-
전체적으로 느낀점 :
문제 접근 방식이 틀렸다.
이진 탐색에는 익숙하지가 않아 이진 탐색과 관련된 문제를 많이 풀어봐야할 것 같다.
이진탐색에 대해 아래에 간략히 설명해봤다.
이진탐색이란?
정렬된 데이터 배열에서 특정한 값을 찾아내기 위해 사용하는 알고리즘이다.
이진탐색의 흐름은 이러하다.
- start, end , mid = (start+end)/2 가 있다.
- 찾고자 하는 값이 mid 와 같다면 종료
mid 보다 크다면 start = mid +1 로 설정하고 위의 1,2를 반복
mid 보다 작다면 end = mid -1 로 설정하고 위의 1,2를 반복
이진탐색을 활용해서 문제를 풀때 고려해야 할 사항들이 있다. 언뜻봐서는 이진탐색으로 푸는 문제라고 풀이를 이끌어내기가 쉽지 않기 때문이다.
이진탐색을 돌릴 기준을 인덱스로 할지 값으로 문제를 보고 잘 정하자.
백준 2512_예산 문제에서는 값을 기준으로 이진탐색을 해야한다. 인덱스를 기준으로 이진탐색을 돌리는 예로는 [1,4,10,17,29] 라는 배열에서 10을 찾아내는 것이다. start = 0, end =4, mid = 2 로 인덱스로 배열에 접근해서
10보다 작으면 end 를 조정하고 크다면 start를 조정해서 10이 있는지 또한 있다면 어디에 있는지 찾아낼 수 있을 것이다.
참고 링크
