2512. 예산
문제
국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.
모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.
예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.
여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.
입력
첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.
출력
첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.
예제 입력 1
4
120 110 140 150
485
예제 출력 1
127
예제 입력 2
5
70 80 30 40 100
450
예제 출력 2
100
알고리즘 분류
- 이분 탐색
- 매개 변수 탐색
코드
n = int(input()) # 지방의 수
arr = list(map(int, input().split())) # 예산 요청
m = int(input()) # 총 예산
start, end = 0, max(arr)
while start <= end: # 이분탐색
mid = (start + end) // 2 # 상한액 설정
curr = 0
for i in arr:
if i >= mid: # 요청한 금액이 상한액 이상이라면
curr += mid # 상한액 더하기
else: # 상한액 미만이라면
curr += i # 요청한 금액 더하기
if curr <= m: # 예산 총액이 총 예산 이하라면
start = mid + 1
else: # 예산 총액이 총 예산을 초과한다면
end = mid - 1
print(end)15810. 풍선 공장
문제
전북대학교 프로그래밍 경진 대회에서는 ACM-ICPC 스타일을 따라 문제를 해결한 팀에게 그 문제에 해당하는 풍선을 달아준다.
풍선을 담당하는 N명의 스태프가 있다. 스태프마다 폐활량이 다르기 때문에 하나의 풍선을 만드는 데 걸리는 시간은 다양하다.
대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰가 들어왔다!
각 스태프가 풍선 하나를 만드는 시간(분) Ai를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까?
풍선을 만든 후에 문제를 표시할 것이기 때문에 풍선의 종류는 상관이 없다.
모든 스태프는 풍선을 만드는 데에 정확하게 자신이 말한 시간만큼 걸린다. 예를 들어 스태프 A가 풍선 하나를 만드는 데 5분이 걸린다면, 0분에 만들기 시작해서 5분에 끝난다.
입력
스태프의 수 N과 풍선의 개수 M이 입력된다. (1 ≤ N, M ≤ 1 000 000)
다음 줄에 N명의 각 스태프들이 풍선 하나를 만드는 데 걸리는 시간 Ai가 순서대로 주어진다. Ai는 1 000 000 이하의 자연수이다.
출력
M개의 풍선이 다 만들어지는 최소 시간을 출력한다.
예제 입력 1
3 8
5 7 3
예제 출력 1
14
힌트
1, 2, 3번 스태프가 각각 5분, 7분, 3분씩 걸린다면 3분이 지났을 때 3번 스태프가 1개, 5분에 1번 스태프가 1개, 6분에 3번 스태프가 1개를, 7분에 2번 스태프가 1개를, 9분에 3번 스태프가 1개를, 10분에 1번 스태프가 1개를, 12분에 3번 스태프가 1개를, 14분에 2번 스태프가 마지막 1개를 만들면 총 14분으로 최소 시간이 걸린다.
알고리즘 분류
- 이분 탐색
- 매개 변수 탐색
코드
def isPossible(time):
balloon=0
for i in arr:
balloon += time//i
if balloon>=M: # 주어진 풍선개수보다 많으면
return True
return False
N,M = map(int,input().split()) # 스태프수, 풍선의 개수
arr = list(map(int,input().split())) # 풍선 만드는데 걸리는 시간
start = 0 # 최소 시간
end = 10000000000000 # 최대 시간
answer = 0
while start<=end:
mid = (start+end)//2
if isPossible(mid):
end = mid-1
answer=mid
else:
start = mid+1
print(int(answer))16564. 히오스 프로게이머
문제
성권이는 Heroes of the Storm 프로게이머 지망생이다.
이 게임에는 총 N개의 캐릭터가 있다. 그리고 현재 각 캐릭터의 레벨은 Xi이다. 성권이는 앞으로 게임이 끝날 때까지, 레벨을 최대 총합 K만큼 올릴 수 있다.
팀 목표레벨 T =min(Xi) (1 ≤ i ≤ N)라고 정의하면, 게임이 끝날 때까지 성권이가 달성할 수 있는 최대 팀 목표레벨 T는 무엇인가?
예를 들어, N = 3, X1= 10, X2= 20, X3= 15이고 K = 10일 때, X1을 7만큼 올리고 X3을 2만큼 올리면 최소 레벨 Xi는 17이 된다. 따라서 팀 목표레벨 T는 17이다. 이 경우처럼 레벨을 총합 K보다 적게 올릴 수도 있다.
입력
첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000)
다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ Xi ≤ 1,000,000,000)
출력
가능한 최대 팀 목표레벨 T를 출력한다.
예제 입력 1
3 10
10
20
15
예제 출력 1
17
알고리즘 분류
- 이분 탐색
- 매개 변수 탐색
코드
N, K = map(int,input().split())
x = [int(input()) for _ in range(N)]
start,end = min(x),max(x)+K # 레벨 최소값, 최대값
while start <= end:
mid = (start+end)//2
need_level = sum([mid-lv for lv in x if mid >= lv]) # 중앙값이 레벨보다 클때만 합한다.
if need_level <= K:
result = mid
start = mid + 1
elif need_level > K:
end = mid - 1
print(result)18869. 멀티버스 Ⅱ
문제
M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다.
두 우주 A와 B가 있고, 우주 A에 있는 행성의 크기는 A1, A2, ..., AN, 우주 B에 있는 행성의 크기는 B1, B2, ..., BN라고 하자. 두 우주의 행성 크기가 모든 1 ≤ i, j ≤ N에 대해서 아래와 같은 조건을 만족한다면, 두 우주를 균등하다고 한다.
Ai < Aj → Bi < Bj
Ai = Aj → Bi = Bj
Ai > Aj → Bi > Bj
입력
첫째 줄에 우주의 개수 M과 각 우주에 있는 행성의 개수 N이 주어진다. 둘째 줄부터 M개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.
출력
첫째 줄에 균등한 우주의 쌍의 개수를 출력한다.
제한
2 ≤ M ≤ 100
3 ≤ N ≤ 10,000
1 ≤ 행성의 크기 ≤ 1,000,000
예제 입력 1
2 3
1 3 2
12 50 31
예제 출력 1
1
- (A, B) = (1, 2)
- A1 = 1 < A2 = 3 이고, B1 = 12 < B2 = 50
- A1 = 1 < A3 = 2 이고, B1 = 12 < B3 = 31
- A2 = 3 > A3 = 2 이고, B2 = 50 > B3 = 31
- 모든 1 ≤ i, j ≤ N에 대해서 만족한다.
예제 입력 2
2 3
1 3 2
12 50 10
예제 출력 2
0
- (A, B) = (1, 2)
- A1 = 1 < A3 = 2 인데, B1 = 12 > B3 = 10이다.
- 모든 1 ≤ i, j ≤ N에 대해서 만족하지 않는다.
예제 입력 3
5 3
20 10 30
10 20 60
80 25 79
30 50 80
80 25 81
예제 출력 3
2
1번과 5번 우주, 2번과 4번 우주가 균등하다.
알고리즘 분류
- 정렬
- 값 / 좌표 압축
코드
from collections import defaultdict
m, n = map(int, input().split())
arr = defaultdict(int) # 딕셔너리 생성
for _ in range(m):
# 행성 입력 받기
planets = list(map(int, input().split()))
# 행성 정렬 ( 구성 같은 행성 한개만 세기 )
sp = sorted(list(set(planets))) # 중복제거
# 행성 순위 지정
rank = {sp[i] : i for i in range(len(sp))} # 0, 1, 2 ...
# 입력 받은 행성에 맞게 순위 저장
vector = tuple([rank[i] for i in planets])
# 해당 순위 벡터에 대한 개수 추가
# vector를 arr 딕셔너리의 키로 사용하여 해당 벡터의 개수를 하나 증가시킨다.
arr[vector] += 1
sum = 0
for i in arr.values():
# n개 중 2개의 우주를 엮어야 하기 때문에 n C 2 를 해줘야 함 (중복 제외)
sum += (i * (i - 1)) // 2 # nC2
print(sum)