백준 2293번

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

2293번: 동전 1

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

arr = [int(input()) for i in range(n)]
dp = [0]*(k+1)


#arr 맨 처음 수로 만들 수 있는 숫자들이 있다면 +1 해줌
for i in range(k+1):
  if i%arr[0]==0:
    dp[i]+=1


# arr의 남은 원소들 사용
for i in range(1,n):
  cur = arr[i]
  # 1부터 k까지 반복
  for j in range(1,k+1):
    # cur이 j이상일 때 (dp[j-cur]음수 방지) 
    if j>=cur:
      #기존 dp[j]에 dp[j-cur]을 더해 줌
      dp[j] = dp[j] + dp[j-cur]


print(dp[k])

arr의 맨 처음 수를 이용하여 k까지 조합해서 만들 수 있는 수들에 +=1을 해주면서 dp설정

 

이 후 arr의 두번 째 수 부 터는 설정 시켜준 dp를 이용함

ex) dp[j] = dp[j] + dp[j-cur]

기존 dp에 dp[j-cur]을 더해줌