2293번: 동전 1

www.acmicpc.net/problem/2293

2293번: 동전 1

동전의 가치들이 n개 만큼 주어지고 주어진 동전들을 활용하여 k값을 만드는 경우가 총 몇개인지 구하는 문제이다.

0-1 Knapsack Problem을 이용하는 DP문제이다.

오랜만에 Knapsack공부하는데 어려웟다...

Knapsack problem 공부용으로 다음 블로그 글을 확인하였다.

blog-st.tistory.com/entry/AL-01-Knapsack-Problem01-%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C

[AL] 0-1 Knapsack Problem(0/1 배낭 문제)

점화식은 다음과 같다.

D(i,k)= if coin[i]>k: D[i][k]=D[i-1][k] else: D[i][k]=D[i-1][k]+D[i][k-coin[i]]

물론 정석은 2차원 배열을 통해 구하는 것이지만,

나는 또 파이썬이라는 위기에 있었다...

처음에 2차원 배열로 구현했다가 메모리 초과,,, 시간초과...

생각을 해보니 D[i] 배열을 구하기 위해서는 사실상 D[i-1]배열만 필요하다는 것을 깨달았다.

그래서 이전 배열을 저장하는 pre_bag 1차원 배열을 만들고, 현재 코인의 1차원 배열을 구하는데 사용하였다. 하지만! 그럼에도 시간초과와 메모리 초과가 났다. 충격....

블로그 버프를 썻더니 배열 하나만으로도 충분히 구현이 가능했다. 블로거님들 너무 똑똑하다. 체고다.

동전 1 code:

import sys
import copy
def solution():
    n,k=map(int,sys.stdin.readline().split())
    coin=[]
    for i in range(n):
        coin.append(int(sys.stdin.readline()))
    len_coin=len(coin)
    bag=[0 for _ in range(k+1)]
    bag[0]=1
    for elem in coin:
        for weight in range(k+1):
            if weight>=elem:
                bag[weight]+=bag[weight-elem] #코인 가치가 무게보다 클 경우
    print(bag[k])#모든 방법의 수


solution()