[백준 알고리즘] 단계별로 풀어보기 - 그리디 알고리즘

모든 문제의 답은 Python3으로 작성함

 

11047번: 동전 0

inp=input().split()
n=int(inp[0])
k=int(inp[1])
digit=[]
for i in range(n):
    digit.append(int(input()))
digit.sort(reverse=True)

sum=0
left=k
for d in digit:
    if left>=d:
        sum += left//d
        left = left%d
        if left==0:
            break
print(sum)

 

1931번: 회의실 배정

n=int(input())
times=[tuple(map(int,input().split())) for _ in range(n)]
times.sort() #회의 시작 시간 기준 정렬
times.sort(key=lambda x:x[1]) #회의 끝 시간 기준 정렬

cur=0 #가장 최근에 한 회의 끝 시간
cnt=0
for t in times:
    if cur<=t[0]: #가장 최근 회의 이후에 시작할 때
        cnt += 1
        cur=t[1]
print(cnt)

예전에 알고리즘 과목에서 다뤘던 예제인데 오랜만에 보니,, 새롭네,,

일찍 시작하는 순서대로 정렬 후, 회의가 빨리 끝나는 순서대로 겹치지 않게 선택!

 

11399번: ATM

n=int(input())
times=list(map(int,input().split()))
times.sort()

cur=0
sum_time=0
for t in times:
    sum_time += cur+t
    cur+=t
print(sum_time)

 

1541번: 잃어버린 괄호

exp=input().split('-')
sum=0
for i in range(len(exp)):
    e=exp[i].split('+')
    if i==0:
        for j in range(len(e)):
            sum+=int(e[j])
    else:
        for k in range(len(e)):
            sum-=int(e[k])
print(sum)

가장 첫번째로 나오는 마이너스 기호 이후를 최솟값으로 만들면 된다.

 

13305번: 주유소

n=int(input())
dis=list(map(int,input().split()))
price=list(map(int,input().split()))

price_sum=price[0]*dis[0]
cur_price=price[0]
for i in range(1,n-1):
    if cur_price>=price[i]:
        cur_price=price[i]
    price_sum+=cur_price*dis[i]
print(price_sum)

가격이 이전 도시에 비해 낮을 때 cur_price 업데이트