본문 바로가기
반응형

알고리즘/그리디30

[백준][Python] 2141번 우체국 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 코드 import sys import math n = int(input()) n_list = [] for _ in range(n): a,b = map(int,sys.stdin.readline().split()) n_list.append([a,b]) n_list.sort() cnt = 0 total = 0 for i in range(n): total += n_list[i][1] fo.. 2022. 4. 29.
[백준][Python] 1092번 배 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 코드 n = int(input()) crane = list(map(int,input().split())) m = int(input()) box = list(map(int,input().split())) crane.sort(reverse=True) box.sort(reverse=True) cnt = 0 if crane[0] 0: cnt+=1 for i in range(n): .. 2022. 4. 28.
[백준][Python] 19598번 최소 회의실 개수 19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의 www.acmicpc.net 코드 import sys import heapq n = int(input()) time = [] for _ in range(n): s,e = map(int,sys.stdin.readline().split()) time.append([s,e]) time.sort() heap = [] cnt = 1 heapq.heappush(heap, time[0][1]) for i in range(1,n): if time[i][0] >= heap[0]: heapq.heapp.. 2022. 4. 27.
[백준][Python] 11509 풍선 맞추기 11509번: 풍선 맞추기 첫 번째 예제 에서 [5,4,3] 을 터트리고 [2,1]을 터트리면 모든 풍선을 터트릴 수 있으므로 최소한 2개의 화살을 필요로 한다. www.acmicpc.net 코드 n = int(input()) n_list = list(map(int,input().split())) arrow = [0] * 1000001 cnt = 0 for i in range(n): if arrow[n_list[i]] == 0: cnt += 1 arrow[n_list[i]-1] += 1 else: arrow[n_list[i]] -= 1 arrow[n_list[i]-1] += 1 print(cnt) 설명 발사된 화살의 위치를 배열을 이용하여 표시해주었다. 만약 주어진 풍선의 높이에 화살이 존재하면 배열에서.. 2022. 4. 13.
반응형

티스토리툴바