백준 9084번 동전

사실 이걸 풀기 전에 동전 1(백준 2293번)을 풀었었다.

 

그 문제를 풀때는 냅색같은 느낌으로 풀었다가 메모리 초과가 나서 1차원으로 풀었었는데

이문제는 둘중 뭘 선택해도 크게 상관없을 듯 하다.

import sys

t=int(sys.stdin.readline().rstrip())
for _ in range(t):
    n=int(sys.stdin.readline().rstrip())
    arr=list(map(int,sys.stdin.readline().rstrip().split()))
    m=int(sys.stdin.readline().rstrip())
    v=[0]*(m+1)
    v[0]=1
    for i in range(n):
        for j in range(arr[i],m+1):
            v[j]+=v[j-arr[i]]
    print(v[m])

구조적으로 1차원이 더빠를 수 밖에 없고 메모리도 덜쓰니까 1차원으로 작성했다.