[백준] 동전 1

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

2293번: 동전 1

다이나믹 프로그래밍을 사용하는 문제입니다. 

 

메모리를 많이주지 않아, 불필요한 할당을 하니 처음에 메모리 초과가 나왔는데 둘다 설명해 보도록 하겠습니다.

우선 문제부터 요약하면, 

 

n가지 종류의 동전으로 가치합을 k로 만드는 경우의 수를 return 해야 합니다. 

1,2,5의 가치를 가진 동전으로 10의 가치를 만드는 경우는 10가지 이므로 10을 return 해야 합니다. 

 

<Solution>

우선 아이디어는 다음과 같습니다. 

다음과 같이 1,2,5의 coin으로 10의 가치를 만드는 경우를 생각해봅시다. 

이 때, 위 그림처럼 표를 구성하게 되면, 점화식을 세울 수 있습니다. 

위 표에서 빨간 두 원을 더한 값이 결과로 들어가는 것을 알 수 있습니다.

(1원만 사용하여 2원을 만드는 경우 + 1원과 2원을 이용하여 (2-2 = 0원)을 만드는 경우)

이 과정을 모든 가치에 대해 해주면 됩니다. 

 

실제 구현은 아래와 같습니다. 이때, 2d array를 구성하여 계산하면 메모리 초과가 발생하므로 1d array를 구성해서 해야 합니다. 

 

<잘못된 풀이>

import sys

n , k = map(int,sys.stdin.readline().rstrip().split())

coin_list = [0]
for i in range(n):
    coin_list.append(int(sys.stdin.readline().rstrip()))

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

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

for p in range(1,n+1):
    for q in range(1,k+1):
        if q - coin_list[p]>=0:
            dp[p][q] = dp[p][q-coin_list[p]] + dp[p-1][q]
        else:
            dp[p][q] = dp[p-1][q]
# print(dp)

print(dp[n][k])

 

<올바른 풀이>

import sys

n , k = map(int,sys.stdin.readline().rstrip().split())

coin_list = []
for i in range(n):
    coin_list.append(int(sys.stdin.readline().rstrip()))

dp = [0] * (k+1)
dp[0] = 1

for coin in coin_list:
    for i in range(1,k+1):
        if i - coin >=0:
            dp[i] = dp[i] + dp[i-coin]
        else:
            continue
# print(dp)
print(dp[k])