그리디 알고리즘

문제 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 (Python) N=int(input()) share=N//5 min_number=N kg5_count,kg3_count=0,0 for i in range(share,-1,-1): if (N-5*i)%3==0: kg5_count=i kg3_count=(N-5*i)//3 if min_number>kg5_count+kg3_count and(kg5_count>0 or kg3_count>0): min_number=kg5_count+kg3_count if kg5_coun..

문제 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 풀이 (Python) n=int(input()) count=0 while n>=0: if n%5==0: #5로 나눠진다면 전부 다 나누기 print(n//5+count) break n-=2 #-2반복 count+=1 #2원을 거슬러 준 횟수를 count에 저장 if n

문제 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 풀이 (Python) n=int(input()) arr=list(input()) def check(): #전체 원소가 같은 색깔인지 점검하는 함수 for i in range(1,len(arr)): if arr[i-1]!=arr[i]: return False return True def paint_count(): arr_B,arr_R,result=0,0,0 if len(arr)==1 or check(): #예외처리 arr가 1개만 입력되거나 전체 원소가 같은..

문제 20115번: 에너지 드링크 페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다. 야근을 마치고 한 www.acmicpc.net 풀이 (Python) #많은 양을 남기고 적은양을 /2값하여 많은 에너지 드링크에 합치면 되는 문제 n=int(input()) arr=list(map(int,input().split())) max_drink=max(arr) arr.remove(max_drink) #제일 큰 값 제외 전부 /2하여 큰값에 더하면 되기 때문에 for ele in arr: #for문을 통해 제일 큰 값에 계속 더해주기 max_drink+=ele/2 print(max_drink) 설..

문제 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 풀이 (Python) arr=list(input()) def poli(): count=0 for i in range(len(arr)): #x의 개수가 4개 연속으로 있다면 A로 대체하기 위한 for문 if arr[i]=="X": count+=1 else: count=0 if count==4: for j in range(4): arr[i-j]="A" count=0 count=0 for i in range(len(arr)): #x의 개수가 3개가 남아있는 case가 있다면 false리턴을 위한 for문 if arr[i]=="X": count+=1 else: cou..