그리디 알고리즘이란?

문제 1 - 거스름 돈

풀이

n = 1260
cnt = 0

arr = [500,100,50,10]

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

print(cnt)

문제 2 - 1이 될 때까지

풀이 1

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

while n >= k:
    while n % k != 0:
        n -= 1
        result += 1
    n //= k
    result += 1

while n > 1:
    n -= 1
    result += 1

print(result)

풀이 2 (시간 복잡도 우수)

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

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

    if n < k:
        break
    result += 1
    n //= k

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

문제 3 - 곱하기 혹은 더하기

풀이

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 - 모험가 길드

풀이

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)