[python] 2293 동전1

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

2293번: 동전 1

 

부분문제

1, 2, 5로 10을 만드는 경우의 수

부분 문제 예시

 

예를 들어 10에서 5를 포함하여 10을 만들 수 있는 경우의 수는

10-5=5이기 때문에 1,2,5로 5를 만들 수 있는 경우의 수와 같다는 것!

1,2,5로 5를 만들 수 있는 경우         ->  5를 포함하여 10을 만들 수 있는 경우

[1,1,1,1,1], [1,1,1,2], [1,2,2], [5]       ->  [1,1,1,1,1,5], [1,1,1,2, 5], [1,2,2, 5], [5,5]

 

*coin[0] = 1 넣어주는건 반복문에서 i==j일때 1을 넣어주기 위함!!(예를들어 5로 5를 표현하는 경우의 수 1개라서)

*꼭 작은 수 부터 안해도 되서 sort()할 필요 없다고 함

n,k = map(int, input().split())
coinType = []
for i in range(n) :
  coinValue = int(input())
  if coinValue <= k :#생략가능
    coinType.append(coinValue)
    
coinType.sort() #생략가능
#print(coinlist)

coin = [0 for i in range(k+1)] #배열 선언
coin[0]=1 #자기자신으로 표현할 수 있는 경우의 수는 1개 이기때문에 시작점을 만들어줌

for i in coinType:
  for j in range(i,k+1):
    if j-i >=0 :
      coin[j] += coin[j-i]
  #print(coin[i])
print(coin[k])

 

n,k = map(int,input().split())
coinlist = [int(input()) for i in range(n)]
    
#print(coinlist)

coin=[0]*(k+1) #배열 선언
coin[0]=1 #coin[0]을 가져오기 위함, 따로 설명

for i in coinlist:
    for j in range(i,k+1):
        coin[j] += coin[j-i]

print(coin[k])