BOJ(동전1,2)(2293)(2294)

작성일 | In

동전 (2293)

  • 1,2,3 더하기4와 동일한 문제
n, m = map(int, input().split())
a = [int(input()) for _ in range(n)]
d = [0] * (m+1)
d[0] = 1
for i in range(n):
    for j in range(m+1):
        if j-a[i] >= 0:
            d[j] += d[j-a[i]]
print(d[m])

동전 2 (2294)

  • D[i] = i원을 만드는데 필요한 동전의 최소개수
n, m = map(int, input().split())
a = [int(input()) for _ in range(n)]
d = [-1] * (m+1)  # d[i]는 i원을 만들 수 있는 경우의 수
d[0] = 0
for i in range(n):
    for j in range(m+1):
        if j-a[i] >= 0 and d[j-a[i]] != -1:
            if d[j] == -1 or d[j] > d[j-a[i]]+1:
                d[j] = d[j-a[i]] + 1
print(d[m])

참고자료 codeplus

0%