14575번: 뒤풀이 첫째 줄에 대회 참가자의 수 N과 술의 총량 T가 주어진다. (1 ≤ N ≤ 1000, 1 ≤ T ≤ 109) 둘째 줄부터 N개의 줄에 걸쳐, 각 사람에 대한 Li와 Ri값이 주어진다. (1 ≤ Li ≤ Ri ≤ 106) www.acmicpc.net 코드 n, t = map(int, input().split()) alcohol = [list(map(int, input().split())) for _ in range(n)] s, e = 1, int(1e9) ans = int(1e9) while s mid: low = -1 break low += alcohol[i][0] high += min(mid, alcohol[i][1]) if low == -1 or high < t: s = mid..
매개변수탐색
1166번: 선물 민식이는 아이들에게 선물할 같은 크기의 작은 박스를 N개 가지고 있다. 모든 작은 박스는 정육면체이고, 크기는 A × A × A 이다. 민식이는 이 작은 박스를 크기가 L × W × H 인 직육면체 박스에 www.acmicpc.net 코드 n, l, w, h = map(int, input().split()) s, e = 0, max(l, w, h) ans = 0 for _ in range(100): mid = (s+e)/2 boxes = (l//mid)*(w//mid)*(h//mid) if boxes < n: e = mid else: ans = mid s = mid print(ans) 이분탐색의 시간복잡도는 $O(logN)$으로 0~1,000,000,000 범위를 탐색한다면 반복문을 1..
2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이..
× 1059번: 좋은 구간 [9, 10], [9, 11], [9, 12], [10, 11], [10, 12] www.acmicpc.net 문제 정수 집합 S가 주어졌을때, 다음 조건을 만족하는 구간 [A, B]를 좋은 구간이라고 한다. A와 B는 양의 정수이고, A < B를 만족한다. A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다. 집합 S와 n이 주어졌을 때, n을 포함하는 좋은 구간의 개수를 구해보자. 입력 첫째 줄에 집합 S의 크기 L이 주어진다. 둘째 줄에는 집합에 포함된 정수가 주어진다. 셋째 줄에는 n이 주어진다. 출력 첫째 줄에 n을 포함하는 좋은 구간의 개수를 출력한다. 제한 1 ≤ L ≤ 50 집합 S에는 중복되는 정수가 없다. 집합 S에 포함된 모든 정수는 1보다..
15810번: 풍선 공장 1, 2, 3번 스태프가 각각 5분, 7분, 3분씩 걸린다면 3분이 지났을 때 3번 스태프가 1개, 5분에 1번 스태프가 1개, 6분에 3번 스태프가 1개를, 7분에 2번 스태프가 1개를, 9분에 3번 스태프가 1개를, 10분에 www.acmicpc.net 문제 전북대학교 프로그래밍 경진 대회에서는 ACM-ICPC 스타일을 따라 문제를 해결한 팀에게 그 문제에 해당하는 풍선을 달아준다. 풍선을 담당하는 N명의 스태프가 있다. 스태프마다 폐활량이 다르기 때문에 하나의 풍선을 만드는 데 걸리는 시간은 다양하다. 대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰가 들어왔다! 각 스태프가 풍선 하나를 만드는 시간(분) $A_i$를 알고 있을 때, 풍선 M개를 만들기 위해서..
