budget

예산

• 문제
• 간단한 문제 설명
  전체 국가 예산과 지방들의 요청 예산들이 주어질 때, 전체 국가 예산을 넘지 않는 선에서 각 지방에게 줄 수 있는 최대 예산을 반환하는 문제. 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150일 때, 상한액을 127로 잡으면 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다. 따라서 127을 반환하면 된다.
• 내 코드
• 내 코드 설명
  출처를 보고 문제를 이해하고 사실상 코드를 다 배낌...ㅠ
  먼저 각 지방의 요청 예산의 합과 최대 요청 예산을 구한다. 요청 예산의 합이 전체 국가 예산을 넘지 않는다면 최대 요청 예산을 반환한다.
  요청 예산의 합이 전체 국자 예산을 넘는다면 이분탐색으로 최대 예산을 구해야한다. 0부터 최대 요청 예산을 범위로 잡고 중간값을 구한다. 각 지방 요청 예산들이 중간값을 넘는다면 요청 예산을 중간값으로 바꾸고 각 지방 요청 예산의 전체 합을 구한다. 이 전체 합이 전제 국가 예산과 같다면 중간값을 반환한다. 전체 합이 전체 국가 예산보다 작다면 전체 합을 임시 변수에 저장하는데 임시 변수의 값보다 클때 저장하며 이때 중간값도 임시 변수에 저장한다. 그리고 탐색 범위 최솟값을 중간값+1로 바꾼다. 전체 합이 전체 국가 예산보다 크다면 탐색범위의 최댓값을 중간값-1로 바꾼다. 이렇게 이분탐색을 탐색범위 최솟값이 최댓값보다 커질 때까지 반복해 최대 예산을 구한다.