'백준/그리디' 카테고리의 글 목록

본문 바로가기

백준 (Baekjoon Online Judge) 그리디 - 11399번 ATM https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 떠올린 아이디어는 간단하다. 일단 입력받은 '인출하는데 필요한 시간'을 오름차순으로 정렬한다. 이후 각 요소를 더해주면 된다. n= int(input()) wt = list(map(int,input().split())) wt.sort() #waitnig time 오름차순으로 정렬 sum=0#대기하는 사람이 인출하는데 걸리는시간 tt=[] for i in range(len(wt)): #대기하는 사람의 수만큼 반복 sum = su..

백준 (Baekjoon Online Judge) 그리디 - 2839번 설탕 배달 설탕배달 문제를 보고 떠올린 아이디어 1. 5KG 봉지로 최대한 담는다. 2. 남은 설탕을 3KG 봉지에 담는다. 였는데... 1kg -> x 2kg -> x 3kg -> 3kg 1개 4kg -> x 5kg -> 5kg 1개 6kg -> 3kg 2개 7kg -> x 8kg -> 5kg 1개, 3kg 1개 9kg -> 3kg 3개... 이런 식으로 진행되는데 일단 5kg에 최대한 담아야 하는 것은 확실하다. 최소한의 봉지 갯수만 사용해야 하니깐. 그래서 남은 3kg에 어떻게 담을것인지 생각해봤는데, 5KG봉지에 최대한 담으면 이후에 세가지 경우의 수가 생긴다. 5kg에 다 담고 3으로 나눈 나머지가 0인 경우 5kg에 다 담고 3으로 나눈 나머지가 1인 경우 5kg에 다 담고 3으로 나눈 나머지가 2인 경..

백준 (Baekjoon Online Judge) 그리디 - 11047번 동전 아이디어 1: 입력받은 큰 돈부터 빼봐야겠다! #시간초과 코드 ㅜㅜ a = list(map(int,input().split())) # coin = [] sum = 0 for i in range(a[0]): money = int(input()) coin.append(money) coin.reverse() for i in coin: while a[1]>=i: #입력받은 b원이 i보다 크면? a[1]=a[1]-i sum+=1 print(sum) 단순하게 가장 큰 돈의 단위부터 계속해서 빼고, 한번 빠질 때마다 sum에 1씩 더하려고 했는데, while 반복문을 돌면서 굉장히 시간적으로 효율이 떨어지는 것을 알 수 있다. 따라서 이런 문제에서 잘 사용할 수 있는 몫을 이용한 방법으로 코드를 다시 구현했다. #성..

티스토리툴바