2293 동전1

백준 2293 동전1

지금까지 풀었던 문제는 dp배열을 한 번만 순회하며 값을 채웠었는데,
이번 문제는 dp배열을 여러번 순회하며 값을 더해나가는 방식이라 이해를 잘 못하고 있었던 것 같다. 내가 처음에 이차원 dp로 생각한것도 무리가 아니다!

이차원 배열

처음엔 dp[i][j] 를 'w[j]원 까지 써서 i원을 만드는 경우의 수'라고 생각하고 점화식을 세워봤다.
dp[i][j] = dp[i-1][j] + dp[i]j-w[i]]

dp[i-1][j] : w[i-1]까지만 쓰고, j원을 만든다. (w[i]원을 무조건 안쓰는 경우의 수)
dp[i][j-w[j]] : w[i]까지만 쓰고, j-w[i]원을 만든다 (w[i]원을 무조건 쓰는 경우의 수, 중복 사용 가능이므로, w[i]원까지 써서 j-w[i]원을 만드는것이 맞다) 

이것을 구현하면 다음과 같다.

n, k = map(int, input().split())
w = [-1]
for _ in range(n):
    w.append(int(input()))

dp = [[0]*(k+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 1

for i in range(1, n+1):
    for j in range(1, k+1):
        dp[i][j] += dp[i-1][j]
        if j >= w[i]:
            dp[i][j] += dp[i][j-w[i]]
            # dp[i-1][j] = dp[i][j]

print(dp)

일차원 배열

근데 위 코드를 자세히 들여다보면, 일차원 배열로 충분히 바꿀 수 있다.
그래서 각 i 단계마다 dp[j]를 갱신하는 점화식을 짜면된다
for i in range(n):
for j in range(k+1):
dp[j] += dp[j-w[i]]

n, k = map(int,input().split())
w = []
for _ in range(n):
    w.append(int(input()))    

dp = [1] + [0 for _ in range(k)]

for i in range(n):
    for j in range(1, k+1):
        if j>=w[i]:
            dp[j] += dp[j-w[i]]
            
print(dp[k])

2294 동전2

동전1과 비슷함
점화식 : dp[i] = min(dp[i-w[j]])+1 for all j s.t. w[j]<=i

근데 이건 i 부터 돌아야함.

n, k = map(int,input().split())
w = []
for _ in range(n):
    w.append(int(input()))    

INF = int(1e9)
dp = [0] + [INF]*(k)

for i in range(1, k+1):
    for j in range(n):
        if w[j]<=i:
            dp[i] = min(dp[i], dp[i-w[j]])
    dp[i] += 1
    
print(dp[k] if dp[k]!=INF+1 else -1)