[Algorithms] 완전탐색(백트랙킹, 상태트리와 CUT EDGE)/깊이우선탐색(DFS) Basic-동전교환(DFS/Cut Edge)

import sys
# sys.stdin=open("input", "r")
input=sys.stdin.readline    # 입력양이 많을 때 이 라인을 쓰면 입력 속도가 빨라진다
# s=input().rstrip()        # 위의 라인을 사용하게 되면 문자열을 읽을 때 줄바꿈 기호가 들어오므로 이를 날려야한다
 
def DFS(level, sum):
    global minimum
    if sum > target:            # sum이 target 금액보다 커지면 return
        return
    if level > minimum:         # CUT EDGE -> minimum level 보다 level이 더 커져버리면
        return                  # 더 이상 볼 필요가 없으므로 return
    if sum == target:           # sum이 target 금액이 된다면 그 개수를 저장
        if minimum > level:
            minimum=level
    else:
        for i in range(types):
            DFS(level+1, sum+coins[i])
 
if __name__=='__main__':
 
    types = int(input())
    coins = list(map(int, input().split()))
    coins.sort(reverse=True)    # 금액이 큰 동전부터 계산하는 것이 빠르게 찾을 수 있으므로
    target = int(input())
    minimum=2147000000
    DFS(0, 0)
    print(minimum)