본문 바로가기

그리디

 (35)
최소 회의실 개수 [백준 19598] https://www.acmicpc.net/problem/19598 heapq를 이용해서 진행되고 있는 강의 중에서 제일 먼저 종료되는 강의들을 찾아내면 된다. import heapq n = int(input()); total = 1; lastend=0 heap =[]; arr =[] for i in range(n): a,b = map(int, input().split()) arr.append((a,b))arr.sort() heapq.heapify(heap)heapq.heappush(heap, arr[0][1]) for start,end in arr[1:] : lastend = heapq.heappop(heap) if lastend
컵라면 [백준 1781] https://www.acmicpc.net/problem/1781 heapq를 잘 사용해서 최대 컵라면 개수를 구해준다. import heapqn = int(input())arr = []for _ in range(n): a, b = map(int, input().split()) arr.append((a, b))arr.sort()heap = []for deadline, cups in arr: heapq.heappush(heap, cups) if len(heap) > deadline: heapq.heappop(heap)print(sum(heap))
강의실[백준 1374] https://www.acmicpc.net/problem/1374  우선순위 큐를 이용하여 문제 해결이 가능하다. import heapq n=int(input())heap1,heap2 = [],[]ans,flag = 0,0for _ in range(n): a,b,c=map(int,input().split()) heapq.heappush(heap1, (b,c))while heap1 : s,e = heapq.heappop(heap1) if flag ==0 : flag += 1; ans +=1 ;heapq.heappush(heap2, (e,s,1)) else : flag += 1 if heap2[0][0]
순회강연 [백준 2109] 처음에 정렬을 날짜말고 가격만 고려해서 정렬하면 된다. 그리고 해당 강연을 최대한 뒤의 날로 정하면 된다. https://www.acmicpc.net/problem/2109 import sysans = [0] * 10001n = int(sys.stdin.readline())data = []for i in range(n): p, d = map(int, sys.stdin.readline().split()) data.append((p, d))data.sort(key= lambda x:-x[0])for p, d in data: while ans[d] != 0: d -= 1 if d != 0: ans[d] = pprint(sum(ans))
공주님의 정원[백준 2457] https://www.acmicpc.net/problem/2457 배열 입력을 받고 순서대로 정렬한 후에 그리디 알고리즘으로 풀면 된다. n = int(input())flowers = []for _ in range(n): flowers.append(list(map(int, input().split())))# 날짜를 정수로 변환 (MMDD 형식으로 변환)def date_to_int(month, day): return month * 100 + day# 꽃의 피는 날과 지는 날을 MMDD 형식으로 변환하여 저장flowers = [(date_to_int(start_month, start_day), date_to_int(end_month, end_day)) for start_month, start_da..
물병[백준 1052] https://www.acmicpc.net/problem/1052 2진수 표현 시 1의 개수가 최종 물병의 개수가 된다. 우리가 목표로 하는 물병 개수가 k개 이라서 그 조건을 만족할 때까지 새로운 물병 (숫자 1)을 더해주면 된다. #include // 1의 개수를 세는 함수int countOnes(unsigned int n) { int count = 0; while (n) { count += n & 1; // n의 마지막 비트가 1인지 확인 n >>= 1; // n을 오른쪽으로 1비트 이동 (즉, 2로 나눔) } return count;}int main() { unsigned int n, k; scanf("%u %u", &n, &k); i..
피보나치[백준 9009] https://www.acmicpc.net/problem/9009  최소의 숫자 개수로 입력받은 수를 만들어야 하니 가장 큰 수부터 배열을 확인하며 내려온다. n = int(input())fibo = [0]*(50)fibo[1] = 1 fibo[2] = 1for i in range(3, 50): fibo[i] = fibo[i-1]+fibo[i-2]def find(k): arr = [] while k>0 : i= 0 for i in range(50): if fibo[i]==k : arr.append(fibo[i]) return arr elif fibo[i] >k : ..
삼각형 만들기[백준 1448] https://www.acmicpc.net/problem/1448  입력받은 수들을 정렬 후에 차례대로 삼각형 결정 조건에 맞는 지 확인한다. n =int(input())arr =[]for _ in range(n): k = int(input()) arr.append(k)arr.sort()arr = arr[::-1]for i in range(n-2): if arr[i]

티스토리툴바