[알고리즘] greedy

(이코테 2021 강의 몰아보기) 2. 그리디 & 구현

greedy : 당장 좋은 것만 고르는 방법
-> 최적의 해를 보장할 수 없을 때가 많음.
-> 그러나 코테에서는 이를 추론할 수 있도록 출제됨.

1번

큰 단위가 항상 작은단위의 배수 -> 큰 화폐단위부터 돈 거슬러주는게 최적해 보장

n = 1260
count = 0

array = [500,100,50,10]

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

시간복잡도 : O(N) 화폐종류만큼

2번

-> N을 k로 나누는 것이 많을 수록 좋음.

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

while True:
  #N이 K로 나누어 떨어지는 수가 될 때까지 빼기 (나누는 연산)
  target = (n//k)*k 
  result += (n - target) 
  n = target

  #n이 k보다 작을 때 (1 빼는 연산)
  if n < k:
  	break
  result += 1
  n //= k

result += (n-1)