이.코.테 바닥공사, 효율적인 화폐 구성(python3)

바닥공사 코드(p. 223)

N = int(input())

data = [0] * 1001
data[1] = 1
data[2] = 3
for i in range(3, N + 1):
    data[i] = (data[i - 1] + 2 * data[i - 2]) % 796796

print(data[N])

 

간단한 dp 문제이다.

 

효율적인 화폐 구성(p. 226)

N, M = map(int, input().split())
money = []
for i in range(N):
    money.append(int(input()))
data = [0] * 10001
for i in money:
    data[i] = 1


for i in range(money[len(money) - 1] + 1, M + 1):
    ans = 10001
    for j in money:
        if data[i - j] != 0:
            ans = min(ans, data[i - j] + 1)
    data[i] = ans


if data[M] == 10001:
    print(-1)
else:
    print(data[M])

money 배열에 화폐를 넣어주고 data배열에 필요로하는 최소의 화폐 개수를 계속 업데이트 해가면 된다.