그리디

그리디 = 탐욕법

<문제1.거스름 돈>

큰 단위가 항상 작은 단위의 배수라서 정당한 방법, 반례 500,400,100일 때 800원이면 큰 단위부터 하면 안됨

n  = 1260
count = 0
arr = [500,100,50,10]

for coin in arr:
  count += n // coin
  n %= coin

print(count)

시간복잡도 O(K), 금액은 무관,동전종류에는 영향 받음

<문제2.1이 될 때까지>

가능하면 최대한 많이 나누는 건 기하급수적으로 빠르게 줄일 수 있으므로 정당함

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

result = 0

while True:
  target = (n//k)*k
  result += (n - target)
  n = target

  if n < k:
    break

  n //= k
  result += 1

result += (n-1)
print(result)

<문제3.곱하기 혹은 더하기>

0과 1일 경우 곱하기보다는 더하기가 더 효율적

data = input()
result = int(data[0])

for i in range(1,len(data)):
  num = int(data[i])
  if num <= 1 or result <= 1: #결과를 조건에 넣는거..
    result += num
  else:
    result *= num

print(result)

<문제4.모험가 길드>

공포도가 x인 모험가는 반드시 x명 이상으로 구성, 그룹 수 최대값

공포도가 오름차순으로 정렬되어 있다는 점에서 항상 최소한의 모험가의 수만 포함하여 그룹을 결성하게 되므로 정당한 방법

그룹에 포함된 모험가 수 >= 확인하고 있는 공포도 수

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

result = 0
count = 0

for i in data:
  count += 1 #현재 그룹에 넣기
  if count >= i: #현재 그룹이 공포도 보다 높다면
    result += 1 #그룹이 되는 것임
    count = 0 #초기화하고 다음 공포도 체크할 준비

print(result)