[백준 2293번] 동전1

n, k = map(int,input().split())

# 1차원 DP 테이블을 사용한 풀이
prices = [0] * n

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

# dp[i] -> i원을 만들 때 가능한 경우의 수
dp = [0 for _ in range(k+1)]
# dp[0] -> 0원을 만들 때 가능한 경우의 수, 동전을 사용하지 않는 경우 이므로 1로 초기화
dp[0] = 1

for price in prices:
    for i in range(price,k+1):
        dp[i] = dp[i] + dp[i-price]
        
print(dp[k])

# 2차원 DP 테이블를 사용한 풀이(시간초과)

# prices = [0] * (n+1)

# for i in range(1,n+1):
#     prices[i] = int(input())

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

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

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

# print(dp[n][k])

이번 문제는 각각의 가치가 다른 n가지 종류의 동전이 있을 때, 이 동전들을 사용해서 k원을 만드는 경우의 수를 구하는 문제이다.

 

DP를 사용하여 풀기 위해 작은 예시부터 직접 계산해보고자 아래와 같이 2차원 DP 테이블을 만들어 채워나가는 방식으로 풀이했다.(n=3, k=5, value = 1 / 2 / 3)

-	-	1	2	3	4	5
-	-	0	0	0	0	0
1	1	1	1	1	1	1
2	1	1	2	2	3	3
3	1	1	2	3	4	5

각 동전의 사용 여부를 결정하기 위해 동전들을 행으로, 1부터 k의 값을 열로 설정하여 각 동전마다 사용하는 경우와 사용하지 않는 경우를 구분하여 DP테이블을 채워나갔다.

 

이를 통해 만약에 현재 동전의 가치가 k값보다 큰 경우(price[i] > j)에는 동전을 사용할 수 없으니 현재 동전을 사용하지 않는 경우의 수(dp[i-1][j])를 저장하고,

현재 동전의 가치가 k값보다 작거나 같은 경우 동전을 사용할 수 있기 때문에 이전까지의 경우의 수(dp[i-1][j])와 동전을 사용하고 난 뒤 남은 값을 만드는 경우의 수(dp[i][j-price[i])를 더한 값을 저장해주었다.

 

문제를 풀다가 떠올리지 못한 가장 중요한 핵심은, 각 행의 dp[0]의 값을 1로 초기화 시켜주는 것이다.(0원을 만드는 경우의 수는 아무 동전도 사용하지 않는 1가지 경우의 수 밖에 존재하지 않기 때문)

 

하지만 2차원 DP 테이블을 사용하여 풀이한 결과, 메모리 초과가 발생하였고 좀 더 메모리를 적게 사용하는 방법으로 문제를 풀이해야 했다.

따라서 DP 테이블을 2차원이 아닌 1차원 리스트로 만들고 초기화한 뒤에 값을 채워나가는 방식으로 풀이하였더니 성공할 수 있었다.

https://woohyun-king.tistory.com/103

[백준 12865번] 평범한 배낭

곰곰히 생각해보면 이 문제는 이전에 풀었던 0-1 배낭 문제와 다르게, 사용하지 않는 경우와 사용하는 경우 중 최대/최소를 구하는 문제가 아니라 k값을 만들 수 있는 경우의 수를 계속해서 쌓아가는 문제이기 때문에 1차원 리스트에 반복해서 채워넣는 방식으로 풀 수 있다.

 

시간은 정말 오래 걸렸지만 DP에 대해 좀 더 깊게 이해해볼 수 있었던 문제였다 :)