[백준] 2293 : 동전 1 (파이썬)

DP 문제

https://www.acmicpc.net/problem/2293

---

💡 풀이코드 (실패 - 메모리 초과)

import sys 
n, k = map(int, sys.stdin.readline().split())
coin = [0] 

for _ in range(n):
    num = int(sys.stdin.readline())
    coin.append(num)

    def sol(n, k, coin):
        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):
                if j - coin[i] < 0: 
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coin[i]]
        print(dp[n][k])
sol(n, k, coin)

---

💡 풀이코드 (성공)

import sys 
n, k = map(int, sys.stdin.readline().split())
coin = [0] 

for _ in range(n):
    num = int(sys.stdin.readline())
    coin.append(num)

def sol(n, k, coin):
    dp = [0] * (k + 1)

    dp[0] = 1

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

 

2차원 배열 -> 1차원 배열로 변경해주니 메모리 초과 문제가 해결되었다.