반응형
2512
https://www.acmicpc.net/problem/2512
2512번: 예산
첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상
www.acmicpc.net
[정답]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
import sys
N = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
c = 0
a.sort()
start = 0
last = a[-1]
while (start <= last):
mid = (start + last)//2
asum = 0
for i in range(len(a)):
if a[i] < mid:
asum += a[i]
else:
asum += mid
if asum > M:
last = mid -1
else:
start = mid+1
print(last)
|
cs |
.
.
.
[풀이]
이분탐색 문제.
이분탐색 루프를 설정하고 for문으로 mid 전 후 값을 따로 합하여 M과 비교한다.
마지막에 예산 중 최댓값을 출력하기 위해 last 값을 출력한다.
p.s.
이분탐색으로 하면 되는 줄 모르고 for로 처음부터 반복했더니 런타임에러가 떴다.
무식하게 하면 안된다.
런타임에러 뜰 때면 이분탐색을 시도해보자.
반응형
'백준 문제풀이' 카테고리의 다른 글
| [백준 19947] 파이썬 : 투자의 귀재 배주형 (0) | 2022.03.12 |
|---|---|
| [백준 24678] 파이썬 : 돌무더기 게임 1 (0) | 2022.03.12 |
| [백준 1417] 파이썬 : 국회의원 선거 (0) | 2022.03.02 |
| [백준 11727] 파이썬 : 2×n 타일링 2 (0) | 2022.03.01 |
| [백준 11728] 파이썬 : 배열 합치기 (0) | 2021.10.27 |