개미전사, 1로 만들기, 효율적인 화폐 구성, 금광(다이나믹)

n=4
array = [1,3,1,5]

d = [0]*100
d[0] = array[0]
d[1] = array[1]
for i in range(2,n):
  d[i] = max(d[i-1], d[i-2]+array[i])

print(d[n-1])

x = 26

d = [0]* 30001

for i in range(2, x+1):
  # 현재 수에서 1을 빼는 경우
  d[i] = d[i-1] + 1
  # 현재 수가 2로 나누어 떨어지는 경우
  if i % 2 == 0:
    d[i] = min(d[i], d[i//2]+1)
  # 현재 수가 3로 나누어 떨어지는 경우
  if i % 3 == 0:
    d[i] = min(d[i], d[i//3]+1)
  # 현재 수가 5로 나누어 떨어지는 경우
  if i % 5 == 0:
    d[i] = min(d[i], d[i//5]+1)

print(d[x])

n=2
m=15
array=[2,3]

d = [10001]*(m+1)
d[0]=0
for i in range(n):
  for j in range(array[i], m+1):
    if d[j - array[i]] != 10001: # (i-k)원을 만드는 방법이 존재하는 경우
      d[j] = min(d[j], d[j -array[i]]+1)

if d[m] == 10001:
  print(-1)
else:
  print(d[m])