그리디 : 가장 최적의 해

<문제> 거스름돈 (큰 단위가 작은 돈의 배수라면)

n = 1260

count = 0

array = [500,100,50,10]

 

for coin in array:

     count += n // coin

     n %= coin

 

print(count)       #화폐의 종류 k -> O(K)

 

 

<곱하기 혹은 더하기>

data = input()

result = int(data[0])

for i in range(1, len(data)):

    num = int(data[i])

    if num <= 1 or result <=1:    #음수나 0일 경우에

       # 더하기

    else:

       # 곱하기

 

 

 

<1이 될 때까지 (N,K) > # 최대한 많이 나누기

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)

 

 

 

 

<모험가>

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

 

 

 

 

4796, 1449, 17509, 11047, 1931, 11000, 1700, 2212, 13904(★), 15748(★), 1493(★)

 

2828