백준 2293 동전 1 (DP)

처음 시도 방법

n, k =[int(v) for v in input().split()]
coins = [0] * n
dp = [[0] * (k+1) for _ in range(n)]

for i in range(n):
    coins[i] = int(input())

for i in range(len(coins)):
    for j in range(1, k+1):
        if j == coins[i]:
            dp[i][j] = dp[i-1][j] + 1
        elif j > coins[i]:
            dp[i][j] = dp[i-1][j] + dp[i][j- coins[i]]
        else:
            dp[i][j] = dp[i-1][j]

print(dp[-1][-1])

냅색 알고리즘을 통해 시도했다.
dp를 2차원 List로 만들고 행은 coin의 개수 열은 0~K까지의 금액이다.
2중 for 문을 돌면서 j 값이 현재 동전의 가치랑 같으면 이전 Dp 값에 + 1
현재 동전의 가치보다 크다면 이전 Dp 값에 현재 행의 J - coin의 DP 값을 더해준다.
그렇지 않은 경우 즉 coin의 가치보다 작은 값은 이전 DP 값을 그대로 저장한다.

이렇게 구하면 답은 맞을 수 있지만 문제에서 주어지는 메모리는 고작 4MB이다. 이럴 시 리스트는 약 1,000,000의 int형 데이터를 저장할 수 있다.

현재 문제를 생각 했을 때 최대 list 필요 양은 n k(100 10,000)로
여유가 없다. 실제로 돌려보면 메모리 초과가 나온다.

그래서 아래와 같이 1차원 List Dp로 문제를 해결해야한다.

n, k =[int(v) for v in input().split()]
coins = [0] * n
dp = [0] * (k+1)

for i in range(n):
    coins[i] = int(input())

dp[0] = 1

for coin in coins:
    for j in range(coin, k+1):
        if j >= coin:
            dp[j] = dp[j] + dp[j - coin]

print(dp[-1])

개념 자체는 똑같다 j 값이 현재 동전의 가치보다 크다면 이전 Dp 값에 현재 행의 J - coin의 DP 값을 더해준다.
하지만 1차원 리스트로 하기 때문에 이전 Dp 값이 현재 인덱스에 이미 저장 되어있다.

---

전혀 생각지도 못한 효율적인 방법이다...