18일차 문제(그리디 풀이)

그리디(Greedy)란?

그리디 알고리즘은 단순하지만 강력한 문제풀이 법이다. 이름에서 유추할 수 있듯이 어떤 문제가 발생할 경우 탐욕적으로 문제를 푸는 알고리즘이다. 즉 현재 상황에서 당장 좋은 것만을 고르는 형태로 현재의 선택이 나중에 미칠 영향을 고려하지 않는다.

첫번째 문제는 동전에 관한 문제로

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

예제 입력 1
10 4200
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 1
6

a,b = map(int,input().split())
emptylist = []
count = 0
for i in range(a):
  c = int(input())
  emptylist.append(c)
for i in list(reversed(emptylist)):
  if b//i >0:
    count += b//i
  else:
    count +=0
  b = b%i
print(count)

먼저 a와 b를 구해준 다음 for문을 통해서 a의 수만큼 돌린다.
그리고 안에 넣어줄 동전의 크기 c를 입력해 준 다음 빈 리스트에 넣어준다.
reversed를 통해서 역순으로 나열하고 동전마다 b를 나눠줬을 때 몫이 1 이상이면 그 몫만큼 count에 더해주었다. 그리고 b의 나머지를 다시 b로 설정한 후 for 문을 돌렸다.

두번째 문제는

1대의 ATM기가 존재하고 사람들의 수가 주어지고 각자 인출하는데 걸리는 시간이 상이하다.
최소의 시간으로 해결할 수 있게 문제를 풀어야 한다.

예제 입력 1
5
3 1 4 3 2
예제 출력 1
32

즉 가장 빨리 끝나는 사람이 앞에서 먼저 돈을 뽑아야 최소 시간대가 구성된다.

a = int(input())
b = sorted(list(map(int, input().split())))
c = 0
emptylist = []
if a ==1:
  print(b[0])
else:
  for i in range(a):
    c +=b[i]
    emptylist.append(c)
  print(sum(emptylist))

for문을 써서 0인 c에 i를 더해주면서 중첩시키고 sum 함수를 써서 총 합계를 냈다.

세번째 문제는

한 학자에게 a번의 강의 제안이 오면 각각의 대학은 강연료와 가능한 날짜를 작성한다. 거기서 최대 수익을 벌 수 있는 경우의 수를 가져와야 한다.

예제 입력 1
7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

예제 출력 1
185

import heapq
a=int(input())
emptylist=[]
for i in range(a):
  emptylist.append(list(map(int, input().split())))
emptylist.sort(key=lambda x: (x[1]))
result=[]
for i in emptylist:
  heapq.heappush(result, i[0])
  if (len(result)>i[1]):
    heapq.heappop(result)
print(sum(result))

heapq를 사용해서 heappop을 사용해서 값이 낮은 숫자는 제거해주고 각각 날짜에 가장 큰 값을 추가한 후 sum을 통해서 다 더해줬다.

네 번째 문제는

한 커피숍은 8시에 문을 열며 그 전까지 손님들이 줄을 선다. 손님들은 자기가 커피를 몇 번째 받는지에 따라 팁을 다른 액수로 팁을 제공한다.
각 손님은 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 준다. 만약, 위의 식으로 나온 값이 음수라면, 팁을 받을 수 없다.

a = int(input())
el = []
result = []
for i in range(a):
  el.append(int(input()))
el = list(reversed(sorted(el)))
for i in range(len(el)):
  if (el[i]-(i+1-1)) >=1:
    result.append((el[i]-(i+1-1)))
  else:
    pass
print(sum(result))

먼저 list를 sorted 한 후 reverse 시켜서 큰 수가 앞에 오게 만들었다. 그 이후 for문을 만들어 각자 자기가 주려했던 돈-(받은 등수 - 1)에 대한 반복문을 작성했다. 만약 그 수가 1보다 크다면 결과에 그 수를 더해주고 0이나 음수면 그냥 pass 하도록 작성했다.