[BAEKJOON] 단계별로 풀어보기 25. 그리디 알고리즘

https://www.acmicpc.net/step/33

그리디 알고리즘 단계

# 11047 : 동전 0

IDEA

가장 큰 화폐 단위부터 나누어 계산한다.

풀이

n, k = map(int, input().split())
count = 0

coin_types = []
for i in range(n):
  coin_types.append(int(input()))

coin_types.sort(reverse=True)

for coin in coin_types:
  count += k // coin
  k %= coin

print(count)
print(coin_types)

• 동전 종류를 입력 받고, 내림차순 정렬을 해준다.
• 가장 큰 단위의 동전부터 몇 개가 필요한지 계산한다.

---

# 1931 : 회의실 배정

IDEA

가장 먼저 끝나는 회의부터 배정, 끝나는 시간이 같다면 먼저 시작하는 회의를 배정한다. (정렬 이용)

풀이

n = int(input())
result = 0

meeting = []
for i in range(n):
  t = list(map(int, input().split()))
  meeting.append(t)

meeting.sort(key=lambda x:(x[1], x[0]))

for i in meeting:
  if result == 0 or i[0] >= start:
    result += 1
    start = i[1]

print(result)

• 회의 시간을 끝나는 시간 -> 시작 시간 순으로 오름차순 정렬한다.
  
  • .sort(key=lambda x: (x[1], x[0])) : x[1]을 기준으로 정렬 후 x[0]을 기준으로 정렬
  • 만약 내림차순으로 정렬하고 싶을 경우, (-x[1], -x[0]) (앞에 -를 붙여주면 됨)
• 가장 먼저 끝나는 회의부터 배정하고, 끝나는 시간이 같다면 먼저 시작하는 회의를 배정한다.

---

# 11399 : ATM

IDEA

돈을 인출하는데 걸리는 시간이 짧은 사람 순서대로 정렬 후 계산한다.

풀이

n = int(input())
data = list(map(int, input().split()))
result = 0

data.sort()

for i in range(n):
  result += sum(data[:i+1])

print(result)

• 각 사람이 돈을 인출하는데 걸리는 시간의 합이 최소가 되려면, 인출하는데 시간이 짧은 사람부터 줄을 서야한다.
  • sort()를 이용하여 리스트를 오름차순 정렬해준 뒤, for문과 sum()함수를 이용하여 각 사람이 기다리는데 필요한 시간의 합을 계산한다. 

---

# 1541 : 잃어버린 괄호

IDEA

괄호를 이용하여 - 뒤에 있는 +를 -로 바꾼다.

풀이

s = input()
result = 0

if s[0] == '-': # 문자열의 처음이 -인 경우
  data = list(s.split('-'))
  data.insert(0, 0)
else:
  data = list(s.split('-'))

for i, n in enumerate(data):
  if i == 0:
    result += sum(list(map(int, n.split('+'))))
  else:
    result -= sum(list(map(int, n.split('+'))))

print(result)

• 문자열을 -를 기준으로 split 해준 뒤, 리스트로 만들어준다.
  • 여기서, 문자열의 처음이 -인 경우(ex. -40+30-20)는 -를 기준으로 split 해준 뒤, 리스트의 맨 첫 번째에 0을 넣어준다.
• 위에서 만든 리스트의 각 원소들에 대하여 +를 기준으로 split 해준 뒤 모든 값들을 더한다.
• 만약 리스트의 첫 번째 원소라면 위의 값을 result에 +, 그게 아니라면 result에 -를 해준다.

---

# 13305 : 주유소

IDEA

첫 번째 주유소에서 주유 후, 그 이후에는 최소 가격의 주유소가 등장할 때마다 주유한다.

풀이

방법 1 (부분 성공)

n = int(input())
dist = list(map(int, input().split()))
price = list(map(int, input().split()))
result = 0

for i in range(n-1):
  result += dist[i]*min(price[:i+1])

print(result)

• for문을 이용하여 각 도시에 도착할 때마다 그 도시 이전의 주유소들에 대하여 가격의 최솟값을 구한 후 계산한다.
  • 2번 서브태스크만 성공, 1, 3번은 시간 초과

방법 2

from sys import stdin

n = int(stdin.readline())
dist = list(map(int, stdin.readline().split()))
price = list(map(int, stdin.readline().split()))
result = 0
cost = price[0]

for i in range(n-1):
  if cost > price[i]:
    cost = price[i]
  result += cost*dist[i]

print(result)

• sys.stdin.readline()이 input() 보다 빠름
  • https://noey-hus.tistory.com/4 #15552 문항 참고
• cost라는 변수를 만들어서 가장 저렴한 가격이 등장할 때마다 cost에 저장 후 금액을 계산한다.
  • 매번 min을 계산하는 것보다 빠른 방법